On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees

被引：28

作者：

Das, G

Goodrich, MT

机构：

[1] JOHNS HOPKINS UNIV, DEPT COMP SCI, BALTIMORE, MD 21218 USA

[2] MEMPHIS STATE UNIV, DEPT MATH SCI, MEMPHIS, TN 38152 USA

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1997年 / 8卷 / 03期

基金：

美国国家科学基金会;

关键词：

convex polyhedra; approximation; Steinitz's theorem; planar graphs; art gallery theorems; decision trees;

D O I：

10.1016/S0925-7721(97)00006-0

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show that several well-known optimization problems involving 3-dimensional convex polyhedra and decision trees are NP-hard or NP-complete. One of the techniques we employ is a linear-time method for realizing a planar 3-connected triangulation as a convex polyhedron, which may be of independent interest. (C) 1997 Published by Elsevier Science B.V.

引用

页码：123 / 137

页数：15

共 42 条

[1]

AGARWAL PK, 1994, PROCEEDINGS OF THE FIFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P24

[2] FINDING MINIMAL CONVEX NESTED POLYGONS [J].

AGGARWAL, A ;

BOOTH, H ;

OROURKE, J ;

SURI, S ;

YAP, CK .

INFORMATION AND COMPUTATION, 1989, 83 (01) :98-110

[3] CONGRUENCE, SIMILARITY, AND SYMMETRIES OF GEOMETRIC OBJECTS [J].

ALT, H ;

MEHLHORN, K ;

WAGENER, H ;

WELZL, E .

DISCRETE & COMPUTATIONAL GEOMETRY, 1988, 3 (03) :237-256

[4]

[Anonymous], 1987, ART GALLERY THEOREMS

[5]

[Anonymous], P 13 INT JOINT C ART

[6] TRAINING A 3-NODE NEURAL NETWORK IS NP-COMPLETE [J].

BLUM, AL ;

RIVEST, RL .

NEURAL NETWORKS, 1992, 5 (01) :117-127

[7]

BONDY JA, 1976, GRAPH THEORY APPLICA

[8]

Breiman L., 1984, Classification and Regression Trees, DOI DOI 10.2307/2530946

[9]

Bronnimann H., 1994, Proceedings of the Tenth Annual Symposium on Computational Geometry, P293, DOI 10.1145/177424.178029

[10]

Chrobak M., 1996, Proceedings of the Twelfth Annual Symposium on Computational Geometry, FCRC '96, P319, DOI 10.1145/237218.237401

← 1 2 3 4 5 →