Exact and approximation algorithms for computing optimal fat decompositions (Q598551): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Import241208061232 (talk | contribs)
Normalize DOI.
 
(3 intermediate revisions by 3 users not shown)
Property / DOI
 
Property / DOI: 10.1016/j.comgeo.2004.01.004 / rank
Normal rank
 
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.comgeo.2004.01.004 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2027037071 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Filling polyhedral molds / rank
 
Normal rank
Property / cites work
 
Property / cites work: Dynamic data structures for fat objects and their applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of the union of fat convex objects in the plane / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient hidden surface removal for objects with small union size / rank
 
Normal rank
Property / cites work
 
Property / cites work: Range Searching and Point Location among Fat Objects / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of the free space for a robot moving amidst fat obstacles / rank
 
Normal rank
Property / cites work
 
Property / cites work: On fat partitioning, fat covering and the union size of polygons / rank
 
Normal rank
Property / cites work
 
Property / cites work: Analysis of a bounding box heuristic for object intersection / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2768316 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fat Triangles Determine Linearly Many Holes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Motion planning in environments with low obstacle density / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4344022 / rank
 
Normal rank
Property / cites work
 
Property / cites work: ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS / rank
 
Normal rank
Property / cites work
 
Property / cites work: Decomposing a Polygon into Simpler Components / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3750120 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4945512 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4401012 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding the medial axis of a simple polygon in linear time / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1016/J.COMGEO.2004.01.004 / rank
 
Normal rank

Latest revision as of 21:55, 9 December 2024

scientific article
Language Label Description Also known as
English
Exact and approximation algorithms for computing optimal fat decompositions
scientific article

    Statements

    Exact and approximation algorithms for computing optimal fat decompositions (English)
    0 references
    0 references
    6 August 2004
    0 references
    The author studies the minimum \(\alpha\)-fat decomposition problem, that is the problem of decomposing a simple polygon into fewest subpolygons, each with aspect ratio \(\alpha\), for a given \(\alpha > 0\). His main result is a polynomial type algorithm that solves the version of this problem that disallows Steiner points. The algorithm returns an optimal \(\alpha\)-fat decomposition, if there is one, otherwise reports failure [cf. \textit{M. van Kreveld}, Comput. Geom. 9, No. 4, 197--210 (1998; Zbl 0894.68155)]. The author also mentions some open problems like (i) Computation of optimal \(\alpha\)-fat decomposition problems that allow Steiner points; (ii) Computation of a minimum \(\alpha\)-fat covering of a simple polygon for a given constant \(\alpha > 0\).
    0 references
    0 references
    polygon decomposition
    0 references
    aspect ratio
    0 references
    fatness
    0 references
    approximation algorithm
    0 references
    Steiner points
    0 references

    Identifiers