Lower bounds for approximate polygon decomposition and minimum gap

Research output: Contribution to journalArticle


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.


Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science


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