Edge-Skeletons in Arrangements with Applications

被引：27

作者：

Edelsbrunner, H. ^{[1
]}

机构：

[1] Graz Tech Univ, Inst Informat Proc, A-8010 Graz, Austria

来源：

ALGORITHMICA | 1986年 / 1卷 / 1-4期

关键词：

Arrangements of planes; Power diagrams; Computational geometry; Asymptotic complexity; Dynamic data structures; Perturbation;

D O I：

10.1007/BF01840438

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

An edge-skeleton in an arrangement A(H) of a finite set of planes in E(3) is a connected collection of edges in A(H). We give a method that constructs a skeleton in O(root n log n) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams in E(2) and space cutting trees in E(3). We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.

引用

页码：93 / 109

页数：17