Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures

摘要: 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. focus on farthest-segment diagram, however, our techniques are also applicable constructing order-\((k{+}1)\) subdivision within order-k region segments and updating a nearest-neighbor diagram deletion one site. Although tree-structured, these illustrate properties surprisingly different from counterparts for points. The relevant forms Davenport-Schinzel order \(\ge 2\). Once this known, we show how compute corresponding in linear time, expected or deterministic, augmenting existing frameworks points convex position ability handle non-point sites multiple faces.