𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Lower bounds for approximate polygon decomposition and minimum gap

✍ Scribed by Joachim Gudmundsson; Thore Husfeldt; Christos Levcopoulos

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
67 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

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 (n log n) lower bound on the timecomplexity. 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 (n log n) time.

πŸ“œ SIMILAR VOLUMES

Triply-Logarithmic Parallel Upper and Lo
Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains
✍ Omer Berkman; Yossi Matias; Prabhakar Ragde πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 193 KB

We consider the problem of computing the minimum of n values, and several w well-known generalizations prefix minima, range minima, and all nearest smaller Ε½ . x w x values ANSV for input elements drawn from the integer domain 1 ΠΈΠΈΠΈ s , where s G n. In this article we give simple and efficient algo