TY - JOUR

T1 - CONVEX PARTITIONS OF POLYHEDRA

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

AU - Chazelle, Bernard

N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

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

VL - 13

SP - 488

EP - 507

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 3

ER -