Two-Dimensional Voronoi Diagrams in the Lp-Metric

No abstract is available for this paper.

• Publication year

  1980

• Venue

  Journal of the ACM

• Publication date

  1980-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/322217.322219
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A New Approach to Planar Point Location

  1981cited by this paper
• Voronoi Diagrams in L1 (Linfty) Metrics with 2-Dimensional Storage Applications

  1980cited by this paper
• An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees

  1979cited by this paper
• On the complexity of computing the measure of ∪[ai,bi]

  1978cited by this paper
• Finding Minimum Spanning Trees

  1976cited by this paper
• Location of a point in a planar subdivision and its applications

  1976cited by this paper
• An O(|E| log log |V|) Algorithm for Finding Minimum Spanning Trees

  1975cited by this paper
• Closest-point problems

  1975cited by this paper
• On the Complexity of Computations under Varying Sets of Primitives

  1975cited by this paper
• Packing and Covering

  1964cited by this paper
• AN ALTERNATIVE METHOD FOR THE CONSTRUCTION OF THIESSEN POLYGONS

  1963cited by this paper
• PRECIPITATION AVERAGES FOR LARGE AREAS

  1911cited by this paper

• Geometric Optimization Frameworks in Mobile Robot Path Planning

  2025cites this paper
• Spatial linear network Voronoi analysis to quantify accessibility of police stations in South Africa

  2025cites this paper
• Designing a sustainable and smart supply chain considering a green computing approach in the post-COVID period

  2025cites this paper
• Farthest-Point Voronoi Diagrams in the Hilbert Metric

  2025cites this paper
• K-Means Featurizer: A booster for intricate datasets

  2024cites this paper
• An optimal algorithm for the minimum-width cubic shell problem

  2023cites this paper
• Voronoi treemap in Manhattan distance and Chebyshev distance

  2023influential citation
• Graph Visualization: Alternative Models Inspired by Bioinformatics

  2023cites this paper
• Polyhedral combinatorics of bisectors

  2023cites this paper
• Chromatic k-Nearest Neighbor Queries

  2022cites this paper
• Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles

  2022cites this paper
• Covering geometric domains

  2021cites this paper
• Voronoi Diagrams

  2021cites this paper
• The Shape and Growth of Forest Trees

  2021cites this paper
• Fused Spatial Point Process Intensity Estimation on Complex Domains

  2021cites this paper
• Fused spatial point process intensity estimation with varying coefficients on complex constrained domains

  2021cites this paper
• Robust Computation of 3D Apollonius Diagrams

  2020cites this paper
• A multiobjective optimization model for sustainable reverse logistics in Indian E-commerce market

  2020cites this paper
• Images of Linear Conditions on a Manhattan Plane

  2020cites this paper
• Computing a Minimum-Width Cubic and Hypercubic Shell

  2019cites this paper
• Bi-objective robust optimization model for configuring cellular manufacturing system with variable machine reliability and parts demand: A real case study

  2019cites this paper
• Computation of Compact Distributions of Discrete Elements

  2019cites this paper
• Empty Squares in Arbitrary Orientation Among Points

  2019cites this paper
• Line Voronoi Diagrams Using Elliptical Distances

  2018cites this paper
• A case against convexity in conceptual spaces

  2017cites this paper
• Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications

  2016cites this paper
• The k-Nearest-Neighbor Voronoi Diagram Revisited

  2015cites this paper
• Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions

  2015cites this paper
• Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions

  2014cites this paper
• On shape Delaunay tessellations

  2014cites this paper
• The Higher-Order Voronoi Diagram of Line Segments

  2014cites this paper
• Competition effects in an afrotemperate forest

  2014cites this paper
• Microscale-calibrated modeling of the deformation response of dual-phase steels

  2014cites this paper
• Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments

  2014cites this paper
• An evaluation of digital elevation modeling in GIS and Cartography

  2014cites this paper
• Fortune’s Method: An Efficient Method For Voronoi Diagram Construction

  2014cites this paper
• Geometric Algorithms for Minimal Enclosing Disks in Strictly Convex Normed Planes

  2014cites this paper
• Higher-order Voronoi diagrams of polygonal objects

  2014cites this paper
• Fortune's Method: An Efficient Method For Voronoi Diagram Construction

  2013cites this paper
• Topological properties of sets represented by an inequality involving distances

  2013cites this paper
• Microscale-calibrated modeling of the deformation response of low-carbon martensite

  2013cites this paper
• VIKOR Method with Enhanced Accuracy for Multiple Criteria Decision Making in Healthcare Management

  2013cites this paper
• Clustering based on a near neighbor graph and a grid cell graph

  2013cites this paper
• A Scheme for Computing Minimum Covers within Simple Regions

  2012cites this paper
• Généralisation du diagramme de Voronoï et placement de formes géométriques complexes dans un nuage de points. (Generalizing the Voronoi diagram and placing complex geometric shapes among a point-set)

  2012influential citation
• On the Farthest Line-Segment Voronoi Diagram

  2012cites this paper
• Tight Bound for Farthest-Color Voronoi Diagrams of Line Segments

  2012cites this paper
• The Stretch Factor of L 1- and L ∞ -Delaunay Triangulations

  2012cites this paper
• On Linear-Sized Farthest-Color Voronoi Diagrams

  2012cites this paper
• The geometric stability of Voronoi diagrams in normed spaces which are not uniformly convex

  2012cites this paper
• A cellular automata based algorithm for voronoi diagram of arbitrary shapes

  2012cites this paper
• Near-pole polar diagram of objects and duality

  2012cites this paper
• Lloyd relaxation using analytical Voronoi diagram in the L ∞ norm and its application to quad optimization

  2012cites this paper
• A note on minimum-sum coverage by aligned disks

  2012cites this paper
• Rescue Boat Voronoi Diagrams for Inhomogeneous, Anisotropic, and Time-Varying Distances

  2011cites this paper
• Skew Jensen-Bregman Voronoi Diagrams

  2011cites this paper
• Continuous-Time Moving Network Voronoi Diagram

  2011cites this paper
• Recursive Algorithm for Determination of Proximal (Thiessen) Polygons in Any Metric Space

  2010cites this paper
• Area-Feature Boundary Labeling

  2010influential citation
• Advances in the Theory of Market Areas

  2010cites this paper
• 3D hyperbolic Voronoi diagrams

  2010cites this paper
• Relaxing and lifting triangulations

  2010cites this paper
• Near Pole Polar Diagram of Points and its Duality with Applications

  2010cites this paper
• Moving Network Voronoi Diagram

  2010cites this paper
• Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric

  2010cites this paper
• Point Location in the Continuous-Time Moving Network

  2010cites this paper
• Boat-Sail Voronoi Diagram and its Application

  2009cites this paper
• Modeling Business Problems with Voronoi Diagrams

  2009cites this paper
• Dislocation density crystalline plasticity modeling of lath martensitic microstructures in steel alloys

  2009cites this paper
• A theoretical structure for computational geometry: regions of point-free overlapping circles

  2009cites this paper
• Optimal-location queries over spatial databases

  2009cites this paper
• Shear pipe effects and dynamic shear-strain localization in martensitic steels

  2009cites this paper
• A Scheme for Computing Minimum Covers within Simple Regions

  2009cites this paper
• An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces

  2009cites this paper
• Area-Feature Boundary Labeling 1

  2009cites this paper
• Modeling of Lath Martensitic Microstructures and Failure Evolution in Steel Alloys

  2009cites this paper
• Analysis of Facility Location Using Ordered Rectilinear Distance in Regular Point Patterns

  2008influential citation
• Path problems in anisotropic regions

  2008cites this paper
• Construction of the segment Delaunay triangulation by a flip algorithm (Construction de la triangulation de Delaunay de segments par un algorithme de flip)

  2008cites this paper
• Refinement of object-based segmentation

  2008cites this paper
• Privacy-Aware RNN Query Processing on Location-Based Services

  2007cites this paper
• Direct Diffusion Method for the Construction of Generalized Voronoi Diagrams

  2007cites this paper
• On Constructing Minimum Spanning Trees in R

  2007cites this paper
• Time Convex Hull with a Highway

  2007cites this paper
• Stable marker-particle method for the Voronoi diagram in a flow field

  2007cites this paper
• The geometry of Minkowski spaces — A survey. Part I

  2007cites this paper
• Computational Geometry Ii

  2007cites this paper
• Mapping with limited sensing

  2007cites this paper
• Combinatorial Geometry with Algorithmic Applications

  2006cites this paper
• Hyperbolic Voronoi Diagram

  2006cites this paper
• Polygon labelling of minimum leader length

  2006cites this paper
• Basic algorithms in computational geometry with imprecise input

  2005cites this paper
• A Digital Vision Chip for Early Feature Extraction with Rotated Template-Matching CA

  2005cites this paper
• Boat-sail Voronoi diagram and its computation based on a cone-approximation scheme

  2005cites this paper
• On Solving Coverage Problems in a Wireless Sensor Network Using Voronoi Diagrams

  2005cites this paper
• The region approach for computing relative neighbourhood graphs in the Lp metric

  2005cites this paper
• Complete Topological Mapping with Sparse Sensing

  2005cites this paper
• Detection of clustered microcalcifications on mammograms using new filter bank

  2005cites this paper
• Boat-Sail Voronoi diagram on a curved surface

  2005cites this paper
• FEM-like Fast Marching Method for the Computation of the Boat-Sail Distance and the Associated Voronoi Diagram

  2004cites this paper