The upper envelope of Voronoi surfaces and its applications
From MaRDI portal
Publication:1207797
DOI10.1007/BF02189323zbMath0770.68111OpenAlexW2014465300MaRDI QIDQ1207797
Klara Kedem, Daniel P. Huttenlocher, Micha Sharir
Publication date: 16 May 1993
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131248
Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Castles in the air revisited, Efficiently approximating color-spanning balls, The L∞ Hausdorff Voronoi Diagram Revisited, Improvements on geometric pattern matching problems, On the parameterized complexity of \(d\)-dimensional point set pattern matching, Applying graphics hardware to achieve extremely fast geometric pattern matching in two and three dimensional transformation space, On the \(k\)-colored rainbow sets in fixed dimensions, Minimum color spanning circle of imprecise points, Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions, Bipartite diameter and other measures under translation, Lower bounds for the complexity of the graph of the Hausdorff distance as a function of transformation, Color spanning objects: algorithms and hardness results, Improved algorithms for the farthest colored Voronoi diagram of segments, On the central path problem, Getting around a lower bound for the minimum Hausdorff distance, On the role of distance transformations in Baddeley's delta metric, Geometric pattern matching in d-dimensional space, Arbitrary-oriented color spanning region for line segments, The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\), Farthest-polygon Voronoi diagrams, Minimum color spanning circle in imprecise setup, Approximate one-to-one point pattern matching, The weighted farthest color Voronoi diagram on trees and graphs., Exact algorithms for the bottleneck Steiner tree problem, Hausdorff matching and Lipschitz optimization, Bottleneck detour tree of points on a path, Stabbing circles for sets of segments in the plane, THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH, Geometric pattern matching under Euclidean motion, Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere, Minimum width color spanning annulus, Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments, Color-spanning localized query, A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation, Improved approximation bounds for planar point pattern matching, Efficient computation of the Hausdorff distance between polytopes by exterior random covering, Unnamed Item, POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD, Unnamed Item, Geometric pattern matching for point sets in the plane under similarity transformations, On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem, Color Spanning Objects: Algorithms and Hardness Results, A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters, Approximate input sensitive algorithms for point pattern matching, Minimum Width Color Spanning Annulus, SMALLEST COLOR-SPANNING OBJECT REVISITED, On exact solutions to the Euclidean bottleneck Steiner tree problem, MAXIMIZING THE AREA OF OVERLAP OF TWO UNIONS OF DISKS UNDER RIGID MOTION, Small candidate set for translational pattern search, Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model, Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding the upper envelope of n line segments in O(n log n) time
- A linear time algorithm for the Hausdorff distance between convex polygons
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- The upper envelope of piecewise linear functions: Algorithms and applications
- Some dynamic computational geometry problems
- Voronoi diagrams and arrangements
- An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Computing the minimum Hausdorff distance between two point sets on a line under translation
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- Congruence, similarity, and symmetries of geometric objects
- Algorithms for Reporting and Counting Geometric Intersections
- Improvements on geometric pattern matching problems
