Edge-skeletons in arrangements with applications
From MaRDI portal
Publication:1091825
DOI10.1007/BF01840438zbMath0623.68059MaRDI QIDQ1091825
Publication date: 1986
Published in: Algorithmica (Search for Journal in Brave)
perturbationgeometric algorithmscomputational geometryVoronoi diagramspower diagramsdynamic data structuresasymptotic complexityarrangements of planesedge-skeletons
Searching and sorting (68P10) Specification and verification (program logics, model checking, etc.) (68Q60) Incidence structures embeddable into projective geometries (51A45)
Related Items
Algorithms for ham-sandwich cuts ⋮ Splitting a configuration in a simplex ⋮ Voronoi diagrams over dynamic scenes ⋮ Computing a ham-sandwich cut in two dimensions ⋮ Selection and sorting in totally monotone arrays ⋮ Tetrahedrizing point sets in three dimensions ⋮ Symbolic treatment of geometric degeneracies ⋮ A geometric consistency theorem for a symbolic perturbation scheme ⋮ Restricted-oriented convex sets ⋮ A new duality result concerning Voronoi diagrams ⋮ Reconstructing Convex Polygons and Polyhedra from Edge and Face Counts in Orthogonal Projections ⋮ Order-k Voronoi diagrams of sites with additive weights in the plane ⋮ On levels in arrangements and Voronoi diagrams ⋮ Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements ⋮ A Complete Implementation for Computing General Dimensional Convex Hulls
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding extreme points in three dimensions and solving the post-office problem in the plane
- Halfspace range search: An algorithmic application of k-sets
- Voronoi diagrams and arrangements
- On the number of line separations of a finite set in the plane
- Voronoi Diagram in the Laguerre Geometry and Its Applications
- Partitioning with two lines in the plane
- Constructing Arrangements of Lines and Hyperplanes with Applications
- On k-Nearest Neighbor Voronoi Diagrams in the Plane
- Convex hulls of finite sets of points in two and three dimensions
- Simple Partitions of Space
- Power Diagrams: Properties, Algorithms and Applications
- Space searching for intersecting objects