\((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity

DOI10.1007/s00454-018-0019-8zbMath1417.68222OpenAlexW2884039401MaRDI QIDQ1731460

Isabelle Sivignon, Dominique Attali, Tuong-Bach Nguyen

Publication date: 13 March 2019

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-018-0019-8

zbMATH Keywords

complexitycoveringmedial axisunion of ballsshape approximationmorphological erosion and dilation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Related Items (1)

Exact and optimal conversion of a hole-free 2\textsc{d} digital object into a union of balls in polynomial time

Uses Software

• CGAL
• 2D Arrangement
• spheretree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New trends in discrete and computational geometry
• Approximation algorithms for combinatorial problems
• Almost optimal set covers in finite VC-dimension
• Exact computation of the medial axis of a polyhedron
• A PTAS for the disk cover problem of geometric objects
• Curvature Measures
• MAXIMIZING THE AREA OF OVERLAP OF TWO UNIONS OF DISKS UNDER RIGID MOTION
• The “λ-medial axis”
• Hierarchical Discrete Medial Axis for Sphere-Tree Construction
• Stability and Computation of Medial Axes - a State-of-the-Art Report
• A Greedy Heuristic for the Set-Covering Problem
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Accurate and efficient unions of balls
• An efficient orthogonal grid drawing algorithm for cubic graphs

This page was built for publication: \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity