| Autor: |
Alevizos, Panagiotis, Boissonnat, Jean-Daniel, Preparata, Franco |
| Zdroj: |
Algorithmica; Jun1990, Vol. 5 Issue 1-4, p573-590, 18p |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink