Diameter, width, closest line pair, and parametric searching
From MaRDI portal
Publication:685180
DOI10.1007/BF02573973zbMATH Open0777.68075MaRDI QIDQ685180FDOQ685180
Authors: Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, 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
Recommendations
Nonlinear programming (90C30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- \(\epsilon\)-nets and simplex range queries
- Applications of random sampling in computational geometry. II
- Parallelism in Comparison Problems
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Optimal Search in Planar Subdivisions
- Randomized optimal algorithm for slope selection
- Slowing down sorting networks to obtain faster sorting algorithms
- Optimal Point Location in a Monotone Subdivision
- On k-Hulls and Related Problems
- On the zone of a surface in a hyperplane arrangement
- Linear Optimization Queries
- Euclidean minimum spanning trees and bichromatic closest pairs
- Title not available (Why is that?)
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- Title not available (Why is that?)
- Selecting distances in the plane
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computing a Segment Center for a Planar Point Set
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (30)
- New lower bounds for Hopcroft's problem
- Linear approximation of simple objects
- Lower Bounds for Geometric Diameter Problems
- APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
- Dynamic half-space range reporting and its applications
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- A note on searching line arrangements and applications
- Efficient randomized algorithms for some geometric optimization problems
- On enclosing k points by a circle
- On range searching with semialgebraic sets
- Largest \(j\)-simplices in \(n\)-polytopes
- On computing the diameter of a point set in high dimensional Euclidean space.
- A deterministic algorithm for the three-dimensional diameter problem
- Computing grasp functions
- All convex polyhedra can be clamped with parallel jaw grippers
- Continuous location of dimensional structures.
- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
- A near-linear algorithm for the planar segment-center problem
- Applications of Parametric Searching in Geometric Optimization
- Optimal parametric search on graphs of bounded tree-width
- Almost tight upper bounds for lower envelopes in higher dimensions
- Fast algorithms for collision and proximity problems involving moving geometric objects
- Title not available (Why is that?)
- Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
- Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
- Using sparsification for parametric minimum spanning tree problems
- On the complexity of some basic problems in computational convexity. I. Containment problems
- Minimum-width double-slabs and widest empty slabs in high dimensions
- Computing the width of a set
- Optimal slope selection via cuttings
This page was built for publication: Diameter, width, closest line pair, and parametric searching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685180)
