Lower bounds for approximate polygon decomposition and minimum gap

Research output: Contribution to journalArticle

Abstract

We consider the problem of decomposing polygons (with holes) into various types of simpler polygons. We focus on the problem of partitioning a rectilinear polygon, with holes, into rectangles, and show an Omega (n log n) lower bound on the time-complexity. The result holds for any decomposition, optimal or approximative. The bound matches the complexity of a number of algorithms in the literature, proving their optimality and settling the complexity of approximate polygon decomposition in these cases. As a related result we show that any non-trivial approximation algorithm for the minimum gap problem requires Omega (n log n) time. (C) 2002 Elsevier Science B.V. All rights reserved.

Details

Authors
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science

Keywords

  • trees, minimum gap, lower bounds, algebraic decision, polygon decomposition, computational geometry
Original languageEnglish
Pages (from-to)137-141
JournalInformation Processing Letters
Volume81
Issue number3
Publication statusPublished - 2002
Publication categoryResearch
Peer-reviewedYes