AN OPTIMAL ALGORITHM FOR THE BOUNDARY OF A CELL IN A UNION OF RAYS

被引：15

作者：

ALEVIZOS, P

BOISSONNAT, JD

PREPARATA, FP

机构：

[1] INST NATL RECH INFORMAT & AUTOMAT,F-06565 VALBONNE,FRANCE

[2] UNIV ILLINOIS,URBANA,IL 61801

[3] ECOLE NORM SUPER,F-75231 PARIS 05,FRANCE

来源：

ALGORITHMICA | 1990年 / 5卷 / 04期

关键词：

Combinatorial geometry; Computational geometry; Union of half-lines;

D O I：

10.1007/BF01840405

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper we study a cell of the subdivision induced by a union of n half-lines (or rays) in the plane. We present two results. The first one is a novel proof of the O(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal Θ(n log n) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right. © 1990 Springer-Verlag New York Inc.

引用

页码：573 / 590

页数：18

共 10 条

[1]

ALEVIZOS P, 1987, 3RD P ACM S COMP GEO, P162

[2]

ATALLAH M, 1983, 24TH P IEEE S F COMP, P99

[3] THE POWER OF GEOMETRIC DUALITY [J].