Approximate minimum diameter

DOI10.1007/978-3-319-62389-4_20MaRDI QIDQ2412413zbMATH OpenOpenAlexFDO

Authors Mohammad Ghodsi, Hamid Homapour, Masoud Seddighin

Publication date 23 October 2017

Full work available at URL https://arxiv.org/abs/1703.10976

zbMATH Keywords

approximation algorithmscomputational geometrycore-setimpreciseindecisive

Mathematics Subject Classification ID

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

Abstract: We study the minimum diameter problem for a set of inexact points. By inexact, we mean that the precise location of the points is not known. Instead, the location of each point is restricted to a contineus region ($impre$ model) or a finite set of points ($indec$ model). Given a set of inexact points in one of $impre$ or $indec$ models, we wish to provide a lower-bound on the diameter of the real points. In the first part of the paper, we focus on $indec$ model. We present an $O(2^{frac1epsilo{n}^d}cdotepsilo{n}^{-2d}cdot{n}^3)$ time approximation algorithm of factor $(1+epsilon)$ for finding minimum diameter of a set of points in $d$ dimensions. This improves the previously proposed algorithms for this problem substantially. Next, we consider the problem in $impre$ model. In $d$-dimensional space, we propose a polynomial time $sqrtd$-approximation algorithm. In addition, for $d=2$, we define the notion of $alpha$-separability and use our algorithm for $indec$ model to obtain $(1+epsilon)$-approximation algorithm for a set of $alpha$-separable regions in time $O(2^{frac1epsilo{n}^2}allowbreak.frac{n}^{3}epsilo{n}^{10}.sin(alpha/2{)}^3)$.

Recommendations

• Diameter and minimal width of the numerical range
• scientific article; zbMATH DE number 7232884
• On size, radius and minimum degree
• Radius, diameter, and minimum degree
• On size, order, diameter and minimum degree
• Average distance, minimum degree, and size
• Minimum Width Rectangular Annulus
• Minimum-width rectangular annulus
• Diameter minimal trees
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS

Cited in

(6)

• Approximation algorithms for color spanning diameter
• Minimizing the diameter of a spanning tree for imprecise points
• Minimum diameter color-spanning sets revisited
• On approximability of minimum color-spanning ball in high dimensions
• A fully polynomial time approximation scheme for the smallest diameter of imprecise points
• scientific article; zbMATH DE number 7232884 (Why is no real title available?)

This page was built for publication: Approximate minimum diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2412413)