The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Lower bounds for approximate polygon decomposition and minimum gap

På svenska

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2002

Language

English

Pages

137-141

Publication/Series

Information Processing Letters

Volume

81

Issue

3

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • trees
  • minimum gap
  • lower bounds
  • algebraic decision
  • polygon decomposition
  • computational geometry

Status

Published

ISBN/ISSN/Other

  • ISSN: 0020-0190