Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements

DOI10.1016/0022-0000(93)90041-TzbMath0795.68190MaRDI QIDQ1317487

Ketan D. Mulmuley

Publication date: 24 March 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

dynamic algorithmsVoronoi diagrams

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Approximation and complexity of the capacitated geometric median problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On levels in arrangements and Voronoi diagrams
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Voronoi diagrams and arrangements
• \(\epsilon\)-nets and simplex range queries
• Edge-skeletons in arrangements with applications
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• Linear Programming in Linear Time When the Dimension Is Fixed
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Shellable Decompositions of Cells and Spheres.