Exact and approximation algorithms for computing optimal fat decompositions

Redirect to:

• Exact and approximation algorithms for computing optimal fat decompositions

DOI10.1016/J.COMGEO.2004.01.004MaRDI QIDQ598551zbMATH OpenOpenAlexFDO

Authors Mirela Damian

Publication date 6 August 2004

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2004.01.004

zbMATH Keywords

approximation algorithmaspect ratiofatnesspolygon decompositionSteiner points

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Approximation algorithms via contraction decomposition
• scientific article; zbMATH DE number 6381654
• scientific article; zbMATH DE number 431496
• Polynomial-time approximation schemes for packing and piercing fat objects
• ‘Fat’ triangulations, or solving certain nonconvex matrix optimization problems
• A randomized FPT approximation algorithm for maximum alternating-cycle decomposition with applications
• scientific article; zbMATH DE number 1594561
• An efficient randomized algorithm for computing the approximate Tucker decomposition
• An approximate decomposition algorithm for convex minimization
• scientific article; zbMATH DE number 5846648

Cites work

• Analysis of a bounding box heuristic for object intersection
• Computing optimal -fat and -small decompositions
• Decomposing a Polygon into Simpler Components
• Dynamic data structures for fat objects and their applications
• Efficient hidden surface removal for objects with small union size
• Fat Triangles Determine Linearly Many Holes
• Filling polyhedral molds
• Finding the medial axis of a simple polygon in linear time
• scientific article; zbMATH DE number 3986641 (Why is no real title available?)
• scientific article; zbMATH DE number 1032051 (Why is no real title available?)
• scientific article; zbMATH DE number 1182915 (Why is no real title available?)
• scientific article; zbMATH DE number 1424299 (Why is no real title available?)
• Motion planning in environments with low obstacle density
• On fat partitioning, fat covering and the union size of polygons
• On the complexity of the union of fat convex objects in the plane
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• Range Searching and Point Location among Fat Objects
• The complexity of the free space for a robot moving amidst fat obstacles

Cited in

(1)

• Minimum star partitions of simple polygons in polynomial time

This page was built for publication: Exact and approximation algorithms for computing optimal fat decompositions

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