Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
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.
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008