Strategies for polyhedral surface decomposition: An experimental study

被引：68

作者：

Chazelle, B

Dobkin, DP

Shouraboura, N

Tal, A

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

[2] PRINCETON UNIV,PROGRAM APPL & COMPUTAT MATH,PRINCETON,NJ 08544

[3] WEIZMANN INST SCI,DEPT COMP SCI,IL-76100 REHOVOT,ISRAEL

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1997年 / 7卷 / 5-6期

基金：

美国国家科学基金会;

关键词：

NP-completeness; 3-SAT; convexity; surface decomposition; flooding heuristics;

D O I：

10.1016/S0925-7721(96)00024-7

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 1997 Elsevier Science B.V.

引用

页码：327 / 342

页数：16

共 21 条

[1]

Amenta N., 1995, Proceedings of the Eleventh Annual Symposium on Computational Geometry, pC12

[2]

[Anonymous], P 9 ANN S COMP GEOM

[3]

[Anonymous], 1987, ART GALLERY THEOREMS

[4] CASTLES IN THE AIR REVISITED [J].