Two-Dimensional Voronoi Diagrams in the L p -Metric

DOI10.1145/322217.322219MaRDI QIDQ3890127zbMATH OpenOpenAlexFDO

Authors

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

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

Mathematics Subject Classification ID

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

Cited in

(61)

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

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

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