✦ LIBER ✦

Tight lower bounds for minimum weight triangulation heuristics

✍ Scribed by Christos Levcopoulos; Drago Krznaric

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 643 KB
Volume: 57
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(95)00200-6

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Tight lower bounds for Shellsort

✍ Mark Allen Weiss; Robert Sedgewick 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 541 KB

Heuristics for planar minimum-weight per

Heuristics for planar minimum-weight perfect metchings

✍ Masao Iri; Kazuo Murota; Shouichi Matsui 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 856 KB

Some lower bounds for constant weight co

Some lower bounds for constant weight codes

✍ Iiro Honkala; Heikki Hämäläinen; Markku Kaikkonen 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 178 KB

Minimum-weight design of hollow cylinder

Minimum-weight design of hollow cylinders for given lower bounds on torsional and flexural rigidities

✍ R.D. Parbery; B.L. Karihaloo 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 612 KB

A greedy heuristic for a minimum-weight

A greedy heuristic for a minimum-weight forest problem

✍ Celina Imielińska; Bahman Kalantari; Leonid Khachiyan 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 382 KB

Lower bounds for approximate polygon dec

Lower bounds for approximate polygon decomposition and minimum gap

✍ Joachim Gudmundsson; Thore Husfeldt; Christos Levcopoulos 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 67 KB

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