Meny

Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Lower bounds for approximate polygon decomposition and minimum gap

Publiceringsår: 2002
Språk: Engelska
Sidor: 137-141
Publikation/Tidskrift/Serie: Information processing letters
Volym: 81
Nummer: 3
Dokumenttyp: Artikel
Förlag: ELSEVIER SCIENCE BV

Sammanfattning

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.

Disputation

Nyckelord

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

Övriga

Published
Yes
  • ISSN: 0020-0190

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen