Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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.
Язык оригинала | английский |
---|---|
Название основной публикации | Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings |
Редакторы | René van Bevern, Gregory Kucherov |
Издатель | Springer Nature |
Страницы | 25-37 |
Число страниц | 13 |
ISBN (печатное издание) | 9783030199548 |
DOI | |
Состояние | Опубликовано - 1 янв 2019 |
Событие | 14th International Computer Science Symposium in Russia, CSR 2019 - Novosibirsk, Российская Федерация Продолжительность: 1 июл 2019 → 5 июл 2019 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 11532 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 14th International Computer Science Symposium in Russia, CSR 2019 |
---|---|
Страна/Tерритория | Российская Федерация |
Город | Novosibirsk |
Период | 1/07/19 → 5/07/19 |
ID: 48856545