A fully polynomial time approximation scheme for the smallest diameter of imprecise points
From MaRDI portal
Publication:2304571
DOI10.1016/j.tcs.2020.02.006zbMath1435.68347OpenAlexW3004921380MaRDI QIDQ2304571
Maarten Löffler, Vahideh Keikha, Ali Mohades
Publication date: 12 March 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.02.006
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
Cause I'm a genial imprecise point: outlier detection for uncertain data ⋮ On the \(k\)-colored rainbow sets in fixed dimensions ⋮ Minimum color spanning circle of imprecise points
Cites Work
- Unnamed Item
- Largest area convex hull of imprecise data based on axis-aligned squares
- The directed Hausdorff distance between imprecise point sets
- Largest and smallest convex hulls for imprecise points
- Triangulating input-constrained planar point sets
- Approximation algorithms for color spanning diameter
- Covering and piercing disks with two centers
- Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
- Computing minimum diameter color-spanning sets is hard
- Largest bounding box, smallest diameter, and related problems on imprecise points
- On the expected diameter, width, and complexity of a stochastic convex hull
- Separability of imprecise points
- On some geometric problems of color-spanning sets
- Convex hulls under uncertainty
- Approximate minimum diameter
- On the Most Likely Convex Hull of Uncertain Points
- Geometric Avatar Problems
- Approximating extent measures of points
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Stochastic minimum spanning trees in euclidean spaces
