Two-Dimensional Voronoi Diagrams in the L _p -Metric

DOI10.1145/322217.322219zbMath0445.68053OpenAlexW2048422125MaRDI QIDQ3890127

No author found.

Publication date: 1980

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322217.322219

zbMATH Keywords

algorithm computational geometry minimum spanning tree nearest neighbor proximity problems smallest circle two-dimensional Voronoi diagrams Lp-metric

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (58)

Voronoi diagrams and arrangements ⋮ An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram ⋮ Voronoi diagrams over dynamic scenes ⋮ An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments ⋮ The region approach for computing relative neighbourhood graphs in the $L_ p$ metric ⋮ The 1-Steiner-Minimal-Tree problem in Minkowski-spaces ⋮ A faster divide-and-conquer algorithm for constructing Delaunay triangulations ⋮ Computation of compact distributions of discrete elements ⋮ A Scheme for Computing Minimum Covers within Simple Regions ⋮ Sorting helps for Voronoi diagrams ⋮ Boat-sail Voronoi diagram on a curved surface ⋮ An analytical solution to the minimum $L_ p$-norm of a hyperplane ⋮ On the asymptotics of quantizers in two dimensions ⋮ On the geodesic Voronoi diagram of point sites in a simple polygon ⋮ Voronoi-like partition of lattice in cellular automata ⋮ ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM ⋮ Stable marker-particle method for the Voronoi diagram in a flow field ⋮ Steiner minimal trees in $L^ 2_ p$ ⋮ On Voronoi diagrams in the $L_p$-metric in $\mathbb{R}^D$. ⋮ A plane-sweep algorithm for finding a closest pair among convex planar objects ⋮ Skew Jensen-Bregman Voronoi Diagrams ⋮ Continuous-Time Moving Network Voronoi Diagram ⋮ A scheme for computing minimum covers within simple regions ⋮ Farthest-point Voronoi diagrams in the presence of rectangular obstacles ⋮ Voronoi diagrams in the moscow metric ⋮ Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions ⋮ A divide-and-conquer algorithm for constructing relative neighborhood graph ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ A case against convexity in conceptual spaces ⋮ Empty squares in arbitrary orientation among points ⋮ Computing the relative neighborhood graph in the $L_ 1$ and L//infinity metrics ⋮ A note on minimum-sum coverage by aligned disks ⋮ A theory of rectangular dual graphs ⋮ Parallel computation of distance transforms ⋮ Proximity problems for points on a rectilinear plane with rectangular obstacles ⋮ Randomized incremental construction of abstract Voronoi diagrams ⋮ Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments ⋮ A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions ⋮ An efficient algorithm for the three-dimensional diameter problem ⋮ On shape Delaunay tessellations ⋮ Representing geometric structures in $d$ dimensions: Topology and order ⋮ Computing a minimum-width cubic and hypercubic shell ⋮ An O(n log n) plane-sweep algorithm for $L_ 1$ and $L_{\infty}$ Delaunay triangulations ⋮ On the construction of abstract Voronoi diagrams ⋮ BOAT-SAIL VORONOI DIAGRAM AND ITS APPLICATION ⋮ Parallel geometric algorithms on a mesh-connected computer ⋮ Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric ⋮ Sparse spatially clustered coefficient model via adaptive regularization ⋮ Extending range queries and nearest neighbors ⋮ The geometry of Minkowski spaces -- a survey. II. ⋮ On computing all north-east nearest neighbors in the $L_ 1$ metric ⋮ Traveling salesman cycles are not always subgraphs of Voronoi duals ⋮ Delaunay triangulation and the convex hull of n points in expected linear time ⋮ Boat-sail Voronoi diagram and its computation based on a cone-approximation scheme ⋮ Triangulation automatique d’un polyèdre en dimension $N$ ⋮ The $k$-nearest-neighbor Voronoi diagram revisited ⋮ The one-dimensional weighted Voronoi diagram ⋮ The higher-order Voronoi diagram of line segments

This page was built for publication: Two-Dimensional Voronoi Diagrams in the L _p -Metric

Two-Dimensional Voronoi Diagrams in the L p -Metric

Two-Dimensional Voronoi Diagrams in the L _p -Metric