Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Linear-time algorithms for the farthest-segment Voronoi diagram and related tree structures. / Khramtcova, Elena; Papadopoulou, Evanthia.
Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings. ред. / Khaled Elbassioni; Kazuhisa Makino. Springer Nature, 2015. стр. 404-414 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 9472).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Linear-time algorithms for the farthest-segment Voronoi diagram and related tree structures
AU - Khramtcova, Elena
AU - Papadopoulou, Evanthia
PY - 2015/1/1
Y1 - 2015/1/1
N2 - We present linear-time algorithms to construct tree-like Voronoi diagrams with disconnected regions after the sequence of their faces along an enclosing boundary (or at infinity) is known. We focus on the farthest-segment Voronoi diagram, however, our techniques are also applicable to constructing the order-(k+1) subdivision within an order-k Voronoi region of segments and updating a nearest-neighbor Voronoi diagram of segments after deletion of one site. Although treestructured, these diagrams illustrate properties surprisingly different from their counterparts for points. The sequence of their faces along the relevant boundary forms a Davenport-Schinzel sequence of order ≥ 2. Once this sequence is known, we show how to compute the corresponding Voronoi diagram in linear time, expected or deterministic, augmenting the existing linear-time frameworks for points in convex position with the ability to handle non-point sites and multiple Voronoi faces.
AB - We present linear-time algorithms to construct tree-like Voronoi diagrams with disconnected regions after the sequence of their faces along an enclosing boundary (or at infinity) is known. We focus on the farthest-segment Voronoi diagram, however, our techniques are also applicable to constructing the order-(k+1) subdivision within an order-k Voronoi region of segments and updating a nearest-neighbor Voronoi diagram of segments after deletion of one site. Although treestructured, these diagrams illustrate properties surprisingly different from their counterparts for points. The sequence of their faces along the relevant boundary forms a Davenport-Schinzel sequence of order ≥ 2. Once this sequence is known, we show how to compute the corresponding Voronoi diagram in linear time, expected or deterministic, augmenting the existing linear-time frameworks for points in convex position with the ability to handle non-point sites and multiple Voronoi faces.
UR - http://www.scopus.com/inward/record.url?scp=84951927944&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-48971-0_35
DO - 10.1007/978-3-662-48971-0_35
M3 - Conference contribution
AN - SCOPUS:84951927944
SN - 9783662489703
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 404
EP - 414
BT - Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings
A2 - Elbassioni, Khaled
A2 - Makino, Kazuhisa
PB - Springer Nature
T2 - 26th International Symposium on Algorithms and Computation, ISAAC 2015
Y2 - 9 December 2015 through 11 December 2015
ER -
ID: 38614641