Lower bounds for approximate polygon decomposition and minimum gap

DOI10.1016/S0020-0190(01)00203-4zbMath1032.68139OpenAlexW2145319911MaRDI QIDQ1603513

Joachim Gudmundsson, Christos Levcopoulos, Thore Husfeldt

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00203-4

zbMATH Keywords

Computational geometryLower boundsAlgebraic decision treesMinimum gapPolygon decomposition

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (1)

FINDING POPULAR PLACES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexities of efficient solutions of rectilinear polygon cover problems
• Triangulating a simple polygon in linear time
• Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles
• Optimal time bounds for some proximity problems in the plane
• Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles
• COVERING CONVEX RECTILINEAR POLYGONS IN LINEAR TIME
• A LINEAR-TIME ALGORITHM FOR COVERING SIMPLE POLYGONS WITH SIMILAR RECTANGLES

This page was built for publication: Lower bounds for approximate polygon decomposition and minimum gap