Diameter, width, closest line pair, and parametric searching

DOI10.1007/BF02573973zbMath0777.68075MaRDI QIDQ685180

Herbert Edelsbrunner, Micha Sharir, Leonidas J. Guibas, Bernard Chazelle

Publication date: 30 September 1993

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131269

zbMATH Keywords

geometric optimizationparametric searching

Mathematics Subject Classification ID

Nonlinear programming (90C30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

On range searching with semialgebraic sets, Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications, Almost tight upper bounds for lower envelopes in higher dimensions, On the complexity of some basic problems in computational convexity. I. Containment problems, Dynamic half-space range reporting and its applications, Using sparsification for parametric minimum spanning tree problems, Largest \(j\)-simplices in \(n\)-polytopes, Optimal parametric search on graphs of bounded tree-width, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS, Computing grasp functions, A deterministic algorithm for the three-dimensional diameter problem, Fast algorithms for collision and proximity problems involving moving geometric objects, All convex polyhedra can be clamped with parallel jaw grippers, Optimal slope selection via cuttings, Continuous location of dimensional structures., Linear approximation of simple objects, A note on searching line arrangements and applications, On enclosing k points by a circle, Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\)., A near-linear algorithm for the planar segment-center problem, Efficient randomized algorithms for some geometric optimization problems, New lower bounds for Hopcroft's problem, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, On computing the diameter of a point set in high dimensional Euclidean space.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\epsilon\)-nets and simplex range queries
• Euclidean minimum spanning trees and bichromatic closest pairs
• Randomized optimal algorithm for slope selection
• On the zone of a surface in a hyperplane arrangement
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• Applications of random sampling in computational geometry. II
• Selecting distances in the plane
• Computing a Segment Center for a Planar Point Set
• Optimal Point Location in a Monotone Subdivision
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• On k-Hulls and Related Problems
• Optimal Search in Planar Subdivisions
• Parallelism in Comparison Problems
• Slowing down sorting networks to obtain faster sorting algorithms
• Linear Optimization Queries