Reconstructing a convex polygon from its omega-cloud

Abstract:

An omega-wedge is the closed set of points contained between two rays that are emanating from a single point (the apex), and are separated by an angle omega < pi. Given a convex polygon P, we place the omega-wedge such that P is inside the wedge and both rays are tangent to P. The omega-cloud of P is the curve traced by the apex of the omega-wedge as it rotates around P while maintaining tangency to both rays.

We investigate reconstructing a polygon P from its omega-cloud. Previous work on reconstructing P from probes with the omega-wedge required knowledge of the points of tangency between P and the two rays of the omega-wedge in addition to the location of the apex. Here  we consider the setting where the maximal omega-cloud alone is given. We determine the conditions under which it uniquely defines P:
(i) when \omega < \pi is fixed/given, or
(ii)  when what is known is that omega < \pi/2.

We show that if neither of these two conditions hold, then P can be not unique. We show that, when the uniqueness conditions hold, the polygon P can be reconstructed in O(n) time with O(1) working space in addition to the input, where n is the number of arcs in the input omega-cloud.

Biography:

Elena Arseneva, previously known as Elena Khramtcova, obtained her specialist degree (considered equal to BSc+MSc) at Mathematics and Mechanics Faculty of Saint-Petersburg State University, Russia.

After that she obtained her PhD at Universita della Svizzera italiana under supervision of Prof. Evanthia Papadopoulou in the area of computational geometry with the main focus in generalized Voronoi diagrams. After completing her PhD studies, she has done a postdoc in the Algorithms Research Group at Université libre de Bruxelles (ULB) hosted by Prof. Stefan Langerman, and funded by the SNF Early PostDoc Mobility program. Currently she is about to start as an Assistant Professor back at Saint-Peretsburg State University, where she will be a part of BSc program in Mathematics and TCS.