Efficient randomized algorithms for some geometric optimization problems
From MaRDI portal
Publication:1816458
DOI10.1007/BF02712871zbMath0857.68109MaRDI QIDQ1816458
Micha Sharir, Pankaj K. Agarwal
Publication date: 26 November 1996
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)
Related Items (32)
On the minimum-area rectangular and square annulus problem ⋮ An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width ⋮ Dynamic coresets ⋮ Rearranging a sequence of points onto a line ⋮ APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS ⋮ COMPUTING ROUNDNESS IS EASY IF THE SET IS ALMOST ROUND ⋮ Minimum dilation stars ⋮ Bipartite diameter and other measures under translation ⋮ Peeling Potatoes Near-Optimally in Near-Linear Time ⋮ Minimum-width rectangular annulus ⋮ Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions ⋮ Precise Hausdorff distance computation between polygonal meshes ⋮ Decomposable multi-parameter matroid optimization problems. ⋮ A (\(1+{\varepsilon}\))-approximation algorithm for 2-line-center ⋮ Continuous location of dimensional structures. ⋮ Computing a minimum-width square annulus in arbitrary orientation ⋮ Fitting a Step Function to a Point Set ⋮ Minimum Width Rectangular Annulus ⋮ Window queries for intersecting objects, maximal points and approximations using coresets ⋮ Minimum width color spanning annulus ⋮ Fitting a step function to a point set ⋮ Unnamed Item ⋮ Minimum-width annulus with outliers: circular, square, and rectangular cases ⋮ Computing a Minimum-Width Square Annulus in Arbitrary Orientation ⋮ Computing a minimum-width cubic and hypercubic shell ⋮ GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS ⋮ Offset-polygon annulus placement problems ⋮ Geometric applications of posets ⋮ Certified efficient global roundness evaluation ⋮ Minimum-width double-strip and parallelogram annulus ⋮ Placing two disks in a convex polygon ⋮ ON THE WIDTH AND ROUNDNESS OF A SET OF POINTS IN THE PLANE
Cites Work
- Diameter, width, closest line pair, and parametric searching
- Optimal slope selection via expanders
- Combinatorial complexity bounds for arrangements of curves and spheres
- Computing the longest diagonal of a simple polygon
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- \(\epsilon\)-nets and simplex range queries
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Randomized optimal algorithm for slope selection
- Generalised regression problems in metrology
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
- Almost tight upper bounds for lower envelopes in higher dimensions
- Optimal slope selection via cuttings
- Applications of random sampling in computational geometry. II
- An algorithm for generalized point location and its applications
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Linear Programming in Linear Time When the Dimension Is Fixed
- Computing the width of a set
- On Collision-Free Placements of Simplices and the Closest Pair of Lines in 3-Space
- Applications of Parametric Searching in Geometric Optimization
- An optimal algorithm for roundness determination on convex polygons
- On lazy randomized incremental construction
- A RANDOMIZED ALGORITHM FOR SLOPE SELECTION
- Unnamed Item
- Unnamed Item
This page was built for publication: Efficient randomized algorithms for some geometric optimization problems
