Strategies for polyhedral surface decomposition: An experimental study

Bernard Chazelle; David P. Dobkin; Nadia Shouraboura; Ayellet Tal

doi:10.1016/S0925-7721(96)00024-7

Strategies for polyhedral surface decomposition: An experimental study

Bernard Chazelle, David P. Dobkin, Nadia Shouraboura, Ayellet Tal

Research output: Contribution to journal › Article

72 Scopus citations

Abstract

This paper addresses the problem of decomposing a complex polyhedral surface into a small number of "convex" patches (i.e., boundary parts of convex polyhedra). The corresponding optimization problem is shown to be NP-complete and an experimental search for good heuristics is undertaken.

Original language	English (US)
Pages (from-to)	327-342
Number of pages	16
Journal	Computational Geometry: Theory and Applications
Volume	7
Issue number	5-6
DOIs	https://doi.org/10.1016/S0925-7721(96)00024-7
State	Published - Apr 1997

All Science Journal Classification (ASJC) codes

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Keywords

3-SAT
Convexity
Flooding heuristics
NP-completeness
Surface decomposition

Access to Document

10.1016/S0925-7721(96)00024-7

Fingerprint Dive into the research topics of 'Strategies for polyhedral surface decomposition: An experimental study'. Together they form a unique fingerprint.

Cite this

@article{43747bbb8da04b18966f3531e127e677,

title = "Strategies for polyhedral surface decomposition: An experimental study",

abstract = "This paper addresses the problem of decomposing a complex polyhedral surface into a small number of {"}convex{"} patches (i.e., boundary parts of convex polyhedra). The corresponding optimization problem is shown to be NP-complete and an experimental search for good heuristics is undertaken.",

keywords = "3-SAT, Convexity, Flooding heuristics, NP-completeness, Surface decomposition",

author = "Bernard Chazelle and Dobkin, {David P.} and Nadia Shouraboura and Ayellet Tal",

year = "1997",

month = apr,

doi = "10.1016/S0925-7721(96)00024-7",

language = "English (US)",

volume = "7",

pages = "327--342",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "5-6",

}

TY - JOUR

T1 - Strategies for polyhedral surface decomposition

T2 - An experimental study

AU - Chazelle, Bernard

AU - Dobkin, David P.

AU - Shouraboura, Nadia

AU - Tal, Ayellet

PY - 1997/4

Y1 - 1997/4

N2 - This paper addresses the problem of decomposing a complex polyhedral surface into a small number of "convex" patches (i.e., boundary parts of convex polyhedra). The corresponding optimization problem is shown to be NP-complete and an experimental search for good heuristics is undertaken.

AB - This paper addresses the problem of decomposing a complex polyhedral surface into a small number of "convex" patches (i.e., boundary parts of convex polyhedra). The corresponding optimization problem is shown to be NP-complete and an experimental search for good heuristics is undertaken.

KW - 3-SAT

KW - Convexity

KW - Flooding heuristics

KW - NP-completeness

KW - Surface decomposition

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

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

U2 - 10.1016/S0925-7721(96)00024-7

DO - 10.1016/S0925-7721(96)00024-7

M3 - Article

AN - SCOPUS:0000957907

VL - 7

SP - 327

EP - 342

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

IS - 5-6

ER -