Lixi Zhou, Jiaqing Chen, et al.
VLDB
In this paper, we present a plane sweep algorithm for constructing the Voronoi diagram of a set of non-crossing line segments in 2D space using a distance metric induced by a regular k-gon and study the robustness of the algorithm. Following the algorithmic degree model [G. Liotta, F.P. Preparata, R. Tamassia, Robust proximity queries: an illustration of degree-driven algorithm design, SIAM J. Comput. 28 (3) (1998) 864-889], we show that the Voronoi diagram of a set of arbitrarily oriented segments can be constructed with degree 14 for certain k-gon metrics (e.g., k=6,8,12). For rectilinear segments or segments with slope +1 or -1, the degree reduces to 2. The algorithm is easy to implement and finds applications in VLSI layout. © 2005 Elsevier B.V. All rights reserved.
Lixi Zhou, Jiaqing Chen, et al.
VLDB
S. Sattanathan, N.C. Narendra, et al.
CONTEXT 2005
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Qing Li, Zhigang Deng, et al.
IEEE T-MI