Qing Li, Zhigang Deng, et al.
IEEE T-MI
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.
Qing Li, Zhigang Deng, et al.
IEEE T-MI
Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012
Pradip Bose
VTS 1998
Xiaozhu Kang, Hui Zhang, et al.
ICWS 2008