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

DOI10.1137/0209017zbMath0447.68111MaRDI 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-completeness; traveling salesman problem; computational geometry; minimum spanning tree; worst-case analysis; Hamiltonian path; approximate algorithm; nearest neighbor method; near-optimal algorithm; average case performance; closest insertion method; open path problem; scheduling of read/write heads; two-dimensional storage medium; voronoi diagram

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68U99: Computing methodologies and applications

68P20: Information storage and retrieval of data

68R99: Discrete mathematics in relation to computer science

Related Items

Finding the largest area axis-parallel rectangle in a polygon, An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations, On the maximum empty rectangle problem, Farthest line segment Voronoi diagrams, Greedy matching on a grid, On computing all north-east nearest neighbors in the \(L_ 1\) metric, Voronoi diagrams and arrangements, An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments, A faster divide-and-conquer algorithm for constructing Delaunay triangulations, On the geodesic Voronoi diagram of point sites in a simple polygon, Voronoi diagrams from convex hulls, Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics, \(L_ 1\) shortest paths among polygonal obstacles in the plane, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance, Sorting helps for Voronoi diagrams, Voronoi-like partition of lattice in cellular automata, Estimation of random fields by piecewise constant estimators, An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram, Voronoi diagrams over dynamic scenes, A combinatorial theorem on labeling squares with points and its application, The geometry of Minkowski spaces -- a survey. II., A Scheme for Computing Minimum Covers within Simple Regions