Edge-skeletons in arrangements with applications

DOI10.1007/BF01840438zbMath0623.68059MaRDI QIDQ1091825

Herbert Edelsbrunner

Publication date: 1986

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

perturbationgeometric algorithmscomputational geometryVoronoi diagramspower diagramsdynamic data structuresasymptotic complexityarrangements of planesedge-skeletons

Mathematics Subject Classification ID

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