Lower bounds for approximate polygon decomposition and minimum gap

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift


title = "Lower bounds for approximate polygon decomposition and minimum gap",
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.",
keywords = "trees, minimum gap, lower bounds, algebraic decision, polygon decomposition, computational geometry",
author = "J Gudmundsson and Thore Husfeldt and Christos Levcopoulos",
year = "2002",
doi = "10.1016/S0020-0190(01)00203-4",
language = "English",
volume = "81",
pages = "137--141",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "3",