ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

An optimal algorithm for the boundary of a cell in a union of rays (1990)

Alevizos, Panagiotis ; Boissonnat, Jean-Daniel ; Preparata, Franco P.

Springer

Algorithmica 5 (1990), S. 573-590

add to mindlist on the mindlist

Details

ISSN: 1432-0541

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

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract In this paper we study a cell of the subdivision induced by a union ofn half-lines (or rays) in the plane. We present two results. The first one is a novel proof of theO(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 logn) 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.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01840405

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit