Advanced

Lower bounds for approximate polygon decomposition and minimum gap

Gudmundsson, J; Husfeldt, Thore LU and Levcopoulos, Christos LU (2002) In Information Processing Letters 81(3). p.137-141
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
trees, minimum gap, lower bounds, algebraic decision, polygon decomposition, computational geometry
in
Information Processing Letters
volume
81
issue
3
pages
137 - 141
publisher
Elsevier
external identifiers
  • wos:000172585600004
  • scopus:0037074659
ISSN
0020-0190
DOI
10.1016/S0020-0190(01)00203-4
language
English
LU publication?
yes
id
93a6d33f-563c-48f8-8d44-385c31dc6898 (old id 348613)
date added to LUP
2007-08-22 08:27:09
date last changed
2017-01-01 07:26:58
@article{93a6d33f-563c-48f8-8d44-385c31dc6898,
  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.},
  author       = {Gudmundsson, J and Husfeldt, Thore and Levcopoulos, Christos},
  issn         = {0020-0190},
  keyword      = {trees,minimum gap,lower bounds,algebraic decision,polygon decomposition,computational geometry},
  language     = {eng},
  number       = {3},
  pages        = {137--141},
  publisher    = {Elsevier},
  series       = {Information Processing Letters},
  title        = {Lower bounds for approximate polygon decomposition and minimum gap},
  url          = {http://dx.doi.org/10.1016/S0020-0190(01)00203-4},
  volume       = {81},
  year         = {2002},
}