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 (25)

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

This page was built for publication: Diameter, width, closest line pair, and parametric searching