Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Reconstructing a convex polygon from its ω -cloud. / Arseneva, Elena; Bose, Prosenjit; De Carufel, Jean Lou; Verdonschot, Sander.
Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. ред. / René van Bevern; Gregory Kucherov. Springer Nature, 2019. стр. 25-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11532 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Reconstructing a convex polygon from its ω -cloud
AU - Arseneva, Elena
AU - Bose, Prosenjit
AU - De Carufel, Jean Lou
AU - Verdonschot, Sander
PY - 2019/1/1
Y1 - 2019/1/1
N2 - An ω -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 ω< π. Given a convex polygon P, we place the ω -wedge such that P is inside the wedge and both rays are tangent to P. The set of apex positions of all such placements of the ω -wedge is called the ω -cloud of P. We investigate reconstructing a polygon P from its ω -cloud. Previous work on reconstructing P from probes with the ω -wedge required knowledge of the points of tangency between P and the two rays of the ω -wedge in addition to the location of the apex. Here we consider the setting where the maximal ω -cloud alone is given. We give two conditions under which it uniquely defines P: (i) when ω< π is fixed/given, or (ii) when what is known is that ω< π/ 2. We show that if neither of these two conditions hold, then P may not be 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 ω -cloud.
AB - An ω -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 ω< π. Given a convex polygon P, we place the ω -wedge such that P is inside the wedge and both rays are tangent to P. The set of apex positions of all such placements of the ω -wedge is called the ω -cloud of P. We investigate reconstructing a polygon P from its ω -cloud. Previous work on reconstructing P from probes with the ω -wedge required knowledge of the points of tangency between P and the two rays of the ω -wedge in addition to the location of the apex. Here we consider the setting where the maximal ω -cloud alone is given. We give two conditions under which it uniquely defines P: (i) when ω< π is fixed/given, or (ii) when what is known is that ω< π/ 2. We show that if neither of these two conditions hold, then P may not be 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 ω -cloud.
KW - TRIANGLES
KW - SHAPE
UR - http://www.scopus.com/inward/record.url?scp=85068603963&partnerID=8YFLogxK
UR - http://www.mendeley.com/research/reconstructing-convex-polygon-%CF%89-cloud
U2 - 10.1007/978-3-030-19955-5_3
DO - 10.1007/978-3-030-19955-5_3
M3 - Conference contribution
AN - SCOPUS:85068603963
SN - 9783030199548
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 25
EP - 37
BT - Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings
A2 - van Bevern, René
A2 - Kucherov, Gregory
PB - Springer Nature
T2 - 14th International Computer Science Symposium in Russia, CSR 2019
Y2 - 1 July 2019 through 5 July 2019
ER -
ID: 48856545