A fully polynomial time approximation scheme for the smallest diameter of imprecise points

DOI10.1016/J.TCS.2020.02.006MaRDI QIDQ2304571zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational geometryapproximation algorithmsimprecise pointsminimum diameter

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

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

Cites work

• Approximate minimum diameter
• Approximating extent measures of points.
• Approximation algorithms for color spanning diameter
• Computing minimum diameter color-spanning sets is hard
• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
• Convex optimization: algorithms and complexity
• Covering and piercing disks with two centers
• Geometric avatar problems
• Largest and smallest convex hulls for imprecise points
• Largest area convex hull of imprecise data based on axis-aligned squares
• Largest bounding box, smallest diameter, and related problems on imprecise points
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• On some geometric problems of color-spanning sets
• On the Most Likely Convex Hull of Uncertain Points
• Separability of imprecise points
• Stochastic minimum spanning trees in Euclidean spaces
• The directed Hausdorff distance between imprecise point sets
• Triangulating input-constrained planar point sets

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)