A fully polynomial time approximation scheme for the smallest diameter of imprecise points
DOI10.1016/J.TCS.2020.02.006zbMATH Open1435.68347OpenAlexW3004921380MaRDI QIDQ2304571FDOQ2304571
Authors: Vahideh Keikha, Maarten Löffler, 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
Recommendations
- Largest bounding box, smallest diameter, and related problems on imprecise points
- Largest Bounding Box, Smallest Diameter, and Related Problems on Imprecise Points
- An optimal deterministic algorithm for computing the diameter of a three-dimensional point set
- Minimizing the diameter of a spanning tree for imprecise points
- Minimizing the diameter of a spanning tree for imprecise points
- A practical approach for computing the diameter of a point set
- Approximating largest convex hulls for imprecise points
- Approximating Largest Convex Hulls for Imprecise Points
- An improved algorithm for approximating the radii of point sets
- Largest and smallest convex hulls for imprecise points
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- Approximating extent measures of points.
- Convex optimization: algorithms and complexity
- Computing minimum diameter color-spanning sets is hard
- On some geometric problems of color-spanning sets
- Largest area convex hull of imprecise data based on axis-aligned squares
- Largest and smallest convex hulls for imprecise points
- Stochastic minimum spanning trees in Euclidean spaces
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- The directed Hausdorff distance between imprecise point sets
- Geometric avatar problems
- Largest bounding box, smallest diameter, and related problems on imprecise points
- On the Most Likely Convex Hull of Uncertain Points
- Triangulating input-constrained planar point sets
- Separability of imprecise points
- Approximation algorithms for color spanning diameter
- Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
- Approximate minimum diameter
- Covering and piercing disks with two centers
Cited In (6)
- Cause I'm a genial imprecise point: outlier detection for uncertain data
- Minimum color spanning circle of imprecise points
- On the \(k\)-colored rainbow sets in fixed dimensions
- Maintaining the minimal distance of a point set in polylogarithmic time
- Minimizing the diameter of a spanning tree for imprecise points
- Minimizing the diameter of a spanning tree for imprecise points
This page was built for publication: A fully polynomial time approximation scheme for the smallest diameter of imprecise points
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2304571)
