Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications

DOI10.1137/0209017zbMath0447.68111OpenAlexW2091757707MaRDI QIDQ3893362

No author found.

Publication date: 1980

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0209017

zbMATH Keywords

NP-completenesstraveling salesman problemcomputational geometryminimum spanning treeworst-case analysisHamiltonian pathapproximate algorithmnearest neighbor methodnear-optimal algorithmaverage case performanceclosest insertion methodopen path problemscheduling of read/write headstwo-dimensional storage mediumvoronoi diagram

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies and applications (68U99) Information storage and retrieval of data (68P20) Discrete mathematics in relation to computer science (68R99)

Related Items

Improved bounds on the stretch factor of \(Y_{4}\), 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, Neighbours on a grid, A faster divide-and-conquer algorithm for constructing Delaunay triangulations, Farthest line segment Voronoi diagrams, A Scheme for Computing Minimum Covers within Simple Regions, Sorting helps for Voronoi diagrams, On the geodesic Voronoi diagram of point sites in a simple polygon, Voronoi-like partition of lattice in cellular automata, Voronoi diagrams from convex hulls, Multidimensional Manhattan preferences, A scheme for computing minimum covers within simple regions, Voronoi diagrams in the moscow metric, Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions, Empty squares in arbitrary orientation among points, Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics, Greedy matching on a grid, Estimation of random fields by piecewise constant estimators, \(L_ 1\) shortest paths among polygonal obstacles in the plane, Voronoi polytopes for polyhedral norms on lattices, Finding the largest area axis-parallel rectangle in a polygon, A combinatorial theorem on labeling squares with points and its application, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance, Computing a minimum-width cubic and hypercubic shell, An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations, The geometry of Minkowski spaces -- a survey. II., On computing all north-east nearest neighbors in the \(L_ 1\) metric, On the maximum empty rectangle problem