CONVEX PARTITIONS OF POLYHEDRA: A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM.

Bernard Chazelle

doi:10.1137/0213031

CONVEX PARTITIONS OF POLYHEDRA: A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM.

Bernard Chazelle

Research output: Contribution to journal › Article › peer-review

186 Scopus citations

Abstract

The problem of partitioning a polyhedron into a minimum number of convex pieces is known to be NP-hard. The author establishes here a quadratic lower bound on the complexity of this problem, and he describes an algorithm that produces a number of convex parts within a constant factor of optimal in the worst case. The algorithm is linear in the size of the polyhedron and cubic in the number of reflex angles. Since in most applications areas, the former quantity greatly exceeds the latter, the algorithm is viable in practice.

Original language	English (US)
Pages (from-to)	488-507
Number of pages	20
Journal	SIAM Journal on Computing
Volume	13
Issue number	3
DOIs	https://doi.org/10.1137/0213031
State	Published - 1984
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0213031

Cite this

@article{be288e1c9960471db3f989817925987e,

title = "CONVEX PARTITIONS OF POLYHEDRA: A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM.",

abstract = "The problem of partitioning a polyhedron into a minimum number of convex pieces is known to be NP-hard. The author establishes here a quadratic lower bound on the complexity of this problem, and he describes an algorithm that produces a number of convex parts within a constant factor of optimal in the worst case. The algorithm is linear in the size of the polyhedron and cubic in the number of reflex angles. Since in most applications areas, the former quantity greatly exceeds the latter, the algorithm is viable in practice.",

author = "Bernard Chazelle",

year = "1984",

doi = "10.1137/0213031",

language = "English (US)",

volume = "13",

pages = "488--507",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - CONVEX PARTITIONS OF POLYHEDRA

T2 - A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM.

AU - Chazelle, Bernard

PY - 1984

Y1 - 1984

N2 - The problem of partitioning a polyhedron into a minimum number of convex pieces is known to be NP-hard. The author establishes here a quadratic lower bound on the complexity of this problem, and he describes an algorithm that produces a number of convex parts within a constant factor of optimal in the worst case. The algorithm is linear in the size of the polyhedron and cubic in the number of reflex angles. Since in most applications areas, the former quantity greatly exceeds the latter, the algorithm is viable in practice.

AB - The problem of partitioning a polyhedron into a minimum number of convex pieces is known to be NP-hard. The author establishes here a quadratic lower bound on the complexity of this problem, and he describes an algorithm that produces a number of convex parts within a constant factor of optimal in the worst case. The algorithm is linear in the size of the polyhedron and cubic in the number of reflex angles. Since in most applications areas, the former quantity greatly exceeds the latter, the algorithm is viable in practice.

UR - http://www.scopus.com/inward/record.url?scp=0021475092&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021475092&partnerID=8YFLogxK

U2 - 10.1137/0213031

DO - 10.1137/0213031

M3 - Article

AN - SCOPUS:0021475092

SN - 0097-5397

VL - 13

SP - 488

EP - 507

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

CONVEX PARTITIONS OF POLYHEDRA: A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this