Lower bounds for approximate polygon decomposition and minimum gap

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Standard

Lower bounds for approximate polygon decomposition and minimum gap. / Gudmundsson, J; Husfeldt, Thore; Levcopoulos, Christos.

I: Information Processing Letters, Vol. 81, Nr. 3, 2002, s. 137-141.

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Harvard

APA

CBE

MLA

Vancouver

Author

RIS

TY - JOUR

T1 - Lower bounds for approximate polygon decomposition and minimum gap

AU - Gudmundsson, J

AU - Husfeldt, Thore

AU - Levcopoulos, Christos

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - trees

KW - minimum gap

KW - lower bounds

KW - algebraic decision

KW - polygon decomposition

KW - computational geometry

U2 - 10.1016/S0020-0190(01)00203-4

DO - 10.1016/S0020-0190(01)00203-4

M3 - Article

VL - 81

SP - 137

EP - 141

JO - Information Processing Letters

T2 - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 3

ER -