Exact and approximation algorithms for minimum-width cylindrical shells

被引：16

作者：

Agarwal, PK

Aronov, B

Sharir, M

机构：

[1] Duke Univ, Dept Comp Sci, Ctr Geometr Comp, Durham, NC 27708 USA

[2] Polytech Univ, Dept Comp & Informat Sci, Brooklyn, NY 11201 USA

[3] Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel

[4] NYU, Courant Inst Math Sci, New York, NY 10012 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2001年 / 26卷 / 03期

关键词：

D O I：

10.1007/s00454-001-0039-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let S be a set of n points in R-3. Let omega* be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S. We first present an O(n(5))-time algorithm for computing omega*, which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n(2+delta))- time algorithm, for any delta > 0, that computes a cylindrical shell of width at most 56 omega* containing S.

引用

页码：307 / 320

页数：14

共 18 条

[1] A Bayesian evolutionary distance for parametrically aligned sequences [J].