On levels in arrangements and Voronoi diagrams

DOI10.1007/BF02574692zbMath0727.68129MaRDI QIDQ804321

Ketan D. Mulmuley

Publication date: 1991

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131161

zbMATH Keywords

arrangement of hyperplanesVoronoi diagrams

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

On the arrangement of stochastic lines in \(\mathbb{R}^2\), A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis, \(k\)-violation linear programming, Dynamic half-space range reporting and its applications, An introduction to randomization in computational geometry, On geometric optimization with few violated constraints, Randomized geometric algorithms and pseudorandom generators, The impact of heterogeneity and geometry on the proof complexity of random satisfiability, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, A simple algorithm for higher-order Delaunay mosaics and alpha shapes, Fully dynamic Delaunay triangulation in logarithmic expected per operation, On the total weight of arrangements of halfplanes, Arrangements of oriented hyperplanes, The \(k\)-nearest-neighbor Voronoi diagram revisited, Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of k-subsets of a set of n points in the plane
• The number of small semispaces of a finite set of points in the plane
• Halfspace range search: An algorithmic application of k-sets
• More on k-sets of finite sets in the plane
• Voronoi diagrams and arrangements
• Edge-skeletons in arrangements with applications
• Voronoi diagrams from convex hulls
• New applications of random sampling in computational geometry
• Constructing Arrangements of Lines and Hyperplanes with Applications
• On k-Hulls and Related Problems
• On k-Nearest Neighbor Voronoi Diagrams in the Plane