APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
From MaRDI portal
Publication:4818546
DOI10.1142/S0218195902000748zbMath1152.68659MaRDI QIDQ4818546
Publication date: 29 September 2004
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Approximation algorithms (68W25)
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 ⋮ CYLINDRICAL HIERARCHY FOR DEFORMING NECKLACES ⋮ Fitting enclosing cylinders to data in \(\mathbb R^n\) ⋮ How to get close to the median shape ⋮ Approximating the discrete center line segment in linear time ⋮ Minimizing the error of linear separators on linearly inseparable data ⋮ Unnamed Item ⋮ Computing a minimum-width square annulus in arbitrary orientation ⋮ FITTING FLATS TO POINTS WITH OUTLIERS ⋮ On finding a large number of 3D points with a small diameter ⋮ THE ALIGNED K-CENTER PROBLEM ⋮ A tight lower bound for computing the diameter of a 3D convex polytope ⋮ Window queries for intersecting objects, maximal points and approximations using coresets ⋮ ON COMPUTING ENCLOSING ISOSCELES TRIANGLES AND RELATED PROBLEMS ⋮ Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points ⋮ Optimizing a constrained convex polygonal annulus ⋮ Minimum-width annulus with outliers: circular, square, and rectangular cases ⋮ Approximating Largest Convex Hulls for Imprecise Points ⋮ Faster core-set constructions and data-stream algorithms in fixed dimensions ⋮ Approximating largest convex hulls for imprecise points ⋮ Computing a Minimum-Width Square Annulus in Arbitrary Orientation ⋮ Practical methods for shape fitting and kinetic data structures using coresets ⋮ Computing a minimum-width cubic and hypercubic shell ⋮ On overlays and minimization diagrams ⋮ GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS ⋮ Robust shape fitting via peeling and grating coresets ⋮ Radii minimal projections of polytopes and constrained optimization of symmetric polynomials ⋮ Certified efficient global roundness evaluation ⋮ Extremal point queries with lines and line segments and related problems ⋮ Streaming algorithms for extent problems in high dimensions
Cites Work
- Diameter, width, closest line pair, and parametric searching
- On ray shooting in convex polytopes
- Small-dimensional linear programming and convex hulls made easy
- Farthest neighbors, maximum spanning trees and related problems in higher dimensions
- Reporting points in halfspaces
- Fitting a set of points by a circle
- Line transversals of balls and smallest enclosing cylinders in three dimensions
- An optimal convex hull algorithm in any fixed dimension
- Efficient randomized algorithms for some geometric optimization problems
- Output-sensitive results on convex hulls, extreme points, and related problems
- Applications of random sampling in computational geometry. II
- A deterministic algorithm for the three-dimensional diameter problem
- Smallest enclosing cylinders
- Linear Programming in Linear Time When the Dimension Is Fixed
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- ON MAINTAINING THE WIDTH AND DIAMETER OF A PLANAR POINT-SET ONLINE
- Applications of Parametric Searching in Geometric Optimization
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Computing Envelopes in Four Dimensions with Applications
- Linear Optimization Queries
- On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
This page was built for publication: APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
