Lower bounds for approximate polygon decomposition and minimum gap

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

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.

Detaljer

Författare
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Sidor (från-till)137-141
TidskriftInformation Processing Letters
Volym81
Utgivningsnummer3
StatusPublished - 2002
PublikationskategoriForskning
Peer review utfördJa