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 条

[31] The Longest Minimum-Weight Path in a Complete Graph
Addario-Berry, Louigi
Broutin, Nicolas
Lugosi, Gabor
COMBINATORICS PROBABILITY & COMPUTING, 2010, 19 (01): : 1 - 19
[32] Minimum-weight beams with shear strain energy
Byoung Koo Lee
Sang Jin Oh
Tae Eun Lee
Jung Su Park
KSCE Journal of Civil Engineering, 2012, 16 : 145 - 154
[33] A GREEDY HEURISTIC FOR A MINIMUM-WEIGHT FOREST PROBLEM
IMIELINSKA, C
KALANTARI, B
KHACHIYAN, L
OPERATIONS RESEARCH LETTERS, 1993, 14 (02) : 65 - 71
[34] On minimum weight pseudo-triangulations
Aichholzer, Oswin
Aurenhammer, Franz
Hackl, Thomas
Speckmann, Bettina
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2009, 42 (6-7): : 627 - 631
[35] A new subgraph of minimum weight triangulations
Wang, CA
Chin, F
Xu, YF
JOURNAL OF COMBINATORIAL OPTIMIZATION, 1997, 1 (02) : 115 - 127
[36] Drawing outerplanar minimum weight triangulations
Lenhart, W
Liotta, G
INFORMATION PROCESSING LETTERS, 1996, 57 (05) : 253 - 260
[37] The drawability problem for minimum weight triangulations
Lenhart, W
Liotta, G
THEORETICAL COMPUTER SCIENCE, 2002, 270 (1-2) : 261 - 286
[38] NONLINEAR MINIMUM-WEIGHT DESIGN OF PLANAR STRUCTURES
VARGO, LG
JOURNAL OF THE AERONAUTICAL SCIENCES, 1956, 23 (10): : 956 - 960
[39] The minimum-weight ideal problem for signed posets
Ando, K
Fujishige, S
Nemoto, T
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 1996, 39 (04) : 558 - 565
[40] Minimum-weight beams with shear strain energy
Lee, Byoung Koo
Oh, Sang Jin
Lee, Tae Eun
Park, Jung Su
KSCE JOURNAL OF CIVIL ENGINEERING, 2012, 16 (01) : 145 - 154

← 1 2 3 4 5 →