ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles  (2)
  • Computational geometry  (2)
  • 1
    Electronic Resource
    Electronic Resource
    An optimal algorithm for the boundary of a cell in a union of rays (1990)
    Springer
    Algorithmica 5 (1990), S. 573-590 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A semidynamic construction of higher-order voronoi diagrams and its randomized analysis (1993)
    Springer
    Algorithmica 9 (1993), S. 329-356 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Dynamic algorithm ; Randomized complexity analysis ; Orderk Voronoi diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the order≤k Voronoi diagrams, can be done inO(n logn+k 3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ⌈(d+1)/2⌉+1 n ⌊(d+1)/2⌋) and space complexityO(k ⌈(d+1)/2⌉ n ⌊(d+1)/2⌋). The algorithm is simple and experimental results are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228508
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...