Approximating Minimum-Weight Triangulations in Three Dimensions

被引：0

作者：

B. Aronov

S. Fortune

机构：

[1] Computer and Information Science,

[2] Polytechnic University,undefined

[3] Brooklyn,undefined

[4] NY 11201,undefined

[5] USA aronov@ziggy.poly.edu,undefined

[6] Bell Laboratories,undefined

[7] Murray Hill,undefined

[8] NJ 07974,undefined

[9] USA sjf@research.bell-labs.com,undefined

来源：

Discrete & Computational Geometry | 1999年 / 21卷

关键词：

Constant Time; Average Cost; Natural Distribution; Similar Connection; Query Line;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Let S be a set of noncrossing triangular obstacles in R3 with convex hull H . A triangulation T of H is compatible with S if every triangle of S is the union of a subset of the faces of T. The weight of T is the sum of the areas of the triangles of T. We give a polynomial-time algorithm that computes a triangulation compatible with S whose weight is at most a constant times the weight of any compatible triangulation.

引用

页码：527 / 549

页数：22

共 50 条

[21] ON GOOD TRIANGULATIONS IN THREE DIMENSIONS
Dey, Tamal Krishna
Bajaj, Chanderjit L.
Sugihara, Kokichi
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1992, 2 (01) : 75 - 95
[22] A new subgraph of minimum weight triangulations
Wang, GA
Chin, EA
Xu, YF
ALGORITHMS AND COMPUTATION, 1996, 1178 : 266 - 274
[23] DESIGN OF DRILLING FACILITIES FOR MINIMUM-WEIGHT PLATFORMS
BOYD, NG
TRANSACTIONS OF THE INSTITUTION OF MINING AND METALLURGY SECTION B-APPLIED EARTH SCIENCE, 1986, 95 : B137 - B138
[24] MINIMUM-WEIGHT DESIGN OF CONTINUOUS COMPOSITE GIRDERS
ITO, M
GALAMBOS, TV
JOURNAL OF STRUCTURAL ENGINEERING-ASCE, 1993, 119 (04): : 1297 - 1311
[25] Elastic Minimum-Weight Annular Plates.
Aristov, M.V.
Troitskii, V.A.
Izvestiya Akademii Nauk, S.S.S.R., Mekhanika Tverdogo Tela, 1975, (03): : 172 - 176
[26] Drawing outerplanar minimum weight triangulations
Department of Computer Science, Williams College, Williamstown, MA 01267, United States
不详
Inf. Process. Lett., 5 (253-260):
[27] Minimum weight pseudo-triangulations
Gudmundsson, J
Levcopoulos, C
FSTTCS 2004: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE, 2004, 3328 : 299 - 310
[28] A New Subgraph of Minimum Weight Triangulations
Cao An Wang
Francis Chin
Yin-Feng Xu
Journal of Combinatorial Optimization, 1997, 1 : 115 - 127
[29] Minimum weight pseudo-triangulations
Gudmundsson, Joachim
Levcopoulos, Christos
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2007, 38 (03): : 139 - 153
[30] MINIMUM WEIGHT DISK TRIANGULATIONS AND FILLINGS
Benjamini, Itai
Lubetzky, Eyal
Peled, Yuval
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2021, 374 (05) : 3265 - 3287

← 1 2 3 4 5 →