On levels in arrangements and Voronoi diagrams

DOI10.1007/BF02574692zbMATH Open0727.68129MaRDI QIDQ804321FDOQ804321

Authors: 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

Recommendations

• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• The complexity of many cells in arrangements of planes and related problems
• On levels in arrangements of lines, segments, planes, and triangles
• On levels in arrangements of surfaces in three dimensions
• On levels in arrangements of surfaces in three dimensions

zbMATH Keywords

Voronoi diagramsarrangement of hyperplanes

Mathematics Subject Classification ID

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

Cites Work

• Voronoi diagrams and arrangements
• New applications of random sampling in computational geometry
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Title not available (Why is that?)
• Voronoi diagrams from convex hulls
• Title not available (Why is that?)
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Title not available (Why is that?)
• On k-Hulls and Related Problems
• Halfspace range search: An algorithmic application of k-sets
• More on k-sets of finite sets in the plane
• 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
• Edge-skeletons in arrangements with applications

Cited In (23)

• Title not available (Why is that?)
• Randomized geometric algorithms and pseudorandom generators
• A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• Fully dynamic Delaunay triangulation in logarithmic expected per operation
• Dynamic half-space range reporting and its applications
• Levelness of Order Polytopes
• On the complexity of the \(k\)-level in arrangements of pseudoplanes
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• The edge labeling of higher order Voronoi diagrams
• \(k\)-violation linear programming
• Arrangements of oriented hyperplanes
• On the arrangement of stochastic lines in \(\mathbb{R}^2\)
• Unbounded regions of high-order Voronoi diagrams of lines and line segments in higher dimensions
• The \(k\)-nearest-neighbor Voronoi diagram revisited
• On geometric optimization with few violated constraints
• On the total weight of arrangements of halfplanes
• Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements
• An introduction to randomization in computational geometry
• Approximating the k-Level in Three-Dimensional Plane Arrangements
• Title not available (Why is that?)
• A simple algorithm for higher-order Delaunay mosaics and alpha shapes
• The Clarkson–Shor Technique Revisited and Extended

This page was built for publication: On levels in arrangements and Voronoi diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804321)