On the Hausdorff Voronoi Diagram of Point Clusters in the Plane
DOI: 10.1007/978-3-540-45078-8_38
关键词:
摘要: We study the Hausdorff Voronoi diagram of point clusters in plane and derive a tight combinatorial bound on its structural complexity. present sweep algorithm for construction this improving upon previous results. Motivation investigation type comes from problem computing critical area VLSI Layout, measure reflecting sensitivity design to spot defects during manufacturing.
sci-hub.se 参考文章(17)
Mark Dubowski, Cathy East Dubowski, The Big Sweep ,(2003)
W. Maly, Computer-aided design for VLSI circuit manufacturability Proceedings of the IEEE. ,vol. 78, pp. 356- 392 ,(1990) , 10.1109/5.52217
Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications ,(2011)
Rolf Klein, Kurt Mehlhorn, Stefan Meiser, Randomized incremental construction of abstract Voronoi diagrams Computational Geometry: Theory and Applications. ,vol. 3, pp. 157- 184 ,(1993) , 10.1016/0925-7721(93)90033-3
F. Dehne, R. Klein, The big sweep : On the power of the wavefront approach to Voronoi diagrams Algorithmica. ,vol. 17, pp. 19- 32 ,(1997) , 10.1007/BF02523236
Michael I. Shamos, Franco P. Preparata, Computational Geometry: An Introduction ,(1978)
Daniel P. Huttenlocher, Klara Kedem, Micha Sharir, The upper envelope of voronoi surfaces and its applications Discrete and Computational Geometry. ,vol. 9, pp. 267- 291 ,(1993) , 10.1007/BF02189323
M. Abellanas, G. Hernandez, R. Klein, V. Neumann-Lara, J. Urrutia, A combinatorial property of convex sets Discrete and Computational Geometry. ,vol. 17, pp. 307- 318 ,(1997) , 10.1007/PL00009296
Steven Fortune, A sweepline algorithm for Voronoi diagrams Algorithmica. ,vol. 2, pp. 153- 174 ,(1987) , 10.1007/BF01840357
H. Walker, S.W. Director, VLASIC: A Catastrophic Fault Yield Simulator for Integrated Circuits IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 5, pp. 541- 556 ,(1986) , 10.1109/TCAD.1986.1270225