@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 Paul} and Nadia Shouraboura and Ayellet Tal",
note = "Funding Information: The classical example is that of cutting up a 3-polyhedron into convex pieces. This is often a useful, sometimes a required, preprocessing step in graphics, manufacturing, and mesh generation. The problem as been exhaustively researched in the last few years \[2-18\].D espite its practical motivation, however, little of that research has gone beyond the theoretical stage. One possible explanation is that even the most naive solutions are programming challenges. We observe, however, that in practice one often need not partition the polyhedron itself but only its boundary. In other words, it often suffices ~ Work by Bernard Chazelle, David Dobkin and Ayellet Tal has been supported in part by NSF Grant CCR-93-01254 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. Work by Nadia Shouraboura has been supported in part by NSF Grant PHY-90-21984. * Corresponding author.",
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 B.V.",
number = "5-6",
}