An algorithm for constructing the convex hull of a set of spheres in dimension d

被引：12

作者：

Boissonnat, JD

Cerezo, A

Devillers, O

Duquesne, J

Yvinec, M

机构：

[1] INRIA,F-06561 VALBONNE,FRANCE

[2] UNIV NICE,F-06034 NICE,FRANCE

[3] CNRS,URA 1376,LAB 13S,F-06560 VALBONNE,FRANCE

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1996年 / 6卷 / 02期

关键词：

computational geometry; convex hull; spheres;

D O I：

10.1016/0925-7721(95)00024-0

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present an algorithm which computes the convex hull of a set of it spheres in dimension d in time O(n([d/2]) + n log n). It is worst-case optimal in three dimensions and in even dimensions. The same method can also be used to compute the convex hull of a set of n homothetic convex objects of E(d). If the complexity of each object is constant, the time needed in the worst case is O(n([d/2]) + n log n).

引用

页码：123 / 130

页数：8

共 8 条

[1]

Boissonnat J.-D., 1992, IFIP C ALG EFF COMP

[2] APPLICATIONS OF RANDOM SAMPLING TO ONLINE ALGORITHMS IN COMPUTATIONAL GEOMETRY [J].