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 条

[1] Approximating minimum-weight triangulations in three dimensions
Aronov, B
Fortune, S
DISCRETE & COMPUTATIONAL GEOMETRY, 1999, 21 (04) : 527 - 549
[2] Triangulations without minimum-weight drawing
Wang, CA
Chin, FY
Yang, BT
INFORMATION PROCESSING LETTERS, 2000, 74 (5-6) : 183 - 189
[3] Triangulations without minimum-weight drawing
Wang, Cao An
Chin, Francis Y.
Yang, Boting
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2000, 1767 : 163 - 173
[4] Triangulations without minimum-weight drawing
Wang, CA
Chin, FY
Yang, BT
ALGORITHMS AND COMPLEXITY, 2000, 1767 : 163 - 173
[5] Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
Department of Computer Science, Lund University, Box 118, S-221 00 Lund, Sweden
J Algorithms, 2 (303-338):
[6] Quasi-greedy triangulations approximating the minimum weight triangulation
Levcopoulos, C
Krznaric, D
PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, : 392 - 401
[7] Quasi-greedy triangulations approximating the minimum weight triangulation
Levcopoulos, C
Krznaric, D
JOURNAL OF ALGORITHMS, 1998, 27 (02) : 303 - 338
[8] Limit theorems for minimum-weight triangulations, other Euclidean Functionals, and probabilistic recurrence relations
Golin, MJ
PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, : 252 - 260
[9] Construction of minimum-weight spanners
Sigurd, M
Zachariasen, M
ALGORITHMS ESA 2004, PROCEEDINGS, 2004, 3221 : 797 - 808
[10] Minimum-Weight Edge Discriminators in Hypergraphs
Bhattacharya, Bhaswar B.
Das, Sayantan
Ganguly, Shirshendu
ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (03):

← 1 2 3 4 5 →