If you do not see this message displayed properly, please click here


The Faculty of Informatics is pleased to announce a seminar given by Elena Arseneva (Khramtcova)



Reconstructing a convex polygon from its omega-cloud
Speaker: Elena Arseneva (Khramtcova)
Universite libre de Bruxelles, Belgium
Date: Thursday, July 19, 2018
Place: USI Lugano Campus, room SI-003, Informatics building (Via G. Buffi 13)
Time: 15:30-16:30



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.



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.


Host: Prof. Evanthia Papadopoulou


Faculty of Informatics

Faculty of Informatics
Università della Svizzera italiana
Via Giuseppe Buffi 13
CH-6904 Lugano
Tel.: +41 (0)58 666 46 90
Fax: +41 (0)58 666 45 36
Email: decanato.inf@usi.ch
Web: www.inf.usi.ch
Twitter: @USI_INF


Segui USI@EXPO2015 su Twitter Segui USI@EXPO2015 su Facebook Segui USI@EXPO2015 su Linkedin Segui USI@EXPO2015 su YouTube