Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

**Reconstructing a convex polygon from its ω -cloud.** / Arseneva, Elena; Bose, Prosenjit; De Carufel, Jean Lou; Verdonschot, Sander.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Arseneva, E, Bose, P, De Carufel, JL & Verdonschot, S 2019, Reconstructing a convex polygon from its ω -cloud. in R van Bevern & G Kucherov (eds), *Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings.* Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11532 LNCS, Springer Nature, pp. 25-37, 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russian Federation, 1/07/19. https://doi.org/10.1007/978-3-030-19955-5_3

Arseneva, E., Bose, P., De Carufel, J. L., & Verdonschot, S. (2019). Reconstructing a convex polygon from its ω -cloud. In R. van Bevern, & G. Kucherov (Eds.), *Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings *(pp. 25-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11532 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-19955-5_3

Arseneva E, Bose P, De Carufel JL, Verdonschot S. Reconstructing a convex polygon from its ω -cloud. In van Bevern R, Kucherov G, editors, Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. Springer Nature. 2019. p. 25-37. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-19955-5_3

@inproceedings{e898b7347778440899e3d191ea8a53d3,

title = "Reconstructing a convex polygon from its ω -cloud",

abstract = "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.",

keywords = "TRIANGLES, SHAPE",

author = "Elena Arseneva and Prosenjit Bose and {De Carufel}, {Jean Lou} and Sander Verdonschot",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-19955-5_3",

language = "English",

isbn = "9783030199548",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature",

pages = "25--37",

editor = "{van Bevern}, Ren{\'e} and Gregory Kucherov",

booktitle = "Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings",

address = "Germany",

note = "14th International Computer Science Symposium in Russia, CSR 2019 ; Conference date: 01-07-2019 Through 05-07-2019",

}

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