Library

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
  • 1
    Electronic Resource
    Electronic Resource
    Fractional cascading: I. A data structuring technique (1986)
    Springer
    Algorithmica 1 (1986), S. 133-162 
    Details
    ISSN: 1432-0541
    Keywords: Binary search ; B-tree ; Iterative search ; Multiple look-up ; Range query ; Dynamization of data structures
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In computational geometry many search problems and range queries can be solved by performing an iterative search for the same key in separate ordered lists. In this paper we show that, if these ordered lists can be put in a one-to-one correspondence with the nodes of a graph of degreed so that the iterative search always proceeds along edges of that graph, then we can do much better than the obvious sequence of binary searches. Without expanding the storage by more than a constant factor, we can build a data-structure, called afractional cascading structure, in which all original searches after the first can be carried out at only logd extra cost per search. Several results related to the dynamization of this structure are also presented. A companion paper gives numerous applications of this technique to geometric problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840440
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Fractional cascading: II. Applications (1986)
    Springer
    Algorithmica 1 (1986), S. 163-191 
    Details
    ISSN: 1432-0541
    Keywords: Fractional cascading ; Iterative search ; Multiple look-up ; Binary search ; B-tree ; Iterative search ; Multiple look-up ; Range query ; Dynamization of data structures
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents several applications offractional cascading, a new searching technique which has been described in a companion paper. The applications center around a variety of geometric query problems. Examples include intersecting a polygonal path with a line, slanted range search, orthogonal range search, computing locus functions, and others. Some results on the optimality of fractional cascading, and certain extensions of the technique for retrieving additional information are also included.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840441
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Randomized incremental construction of Delaunay and Voronoi diagrams (1992)
    Springer
    Algorithmica 7 (1992), S. 381-413 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Voronoi diagram ; randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give a new randomized incremental algorithm for the construction of planar Voronoi diagrams and Delaunay triangulations. The new algorithm is more “on-line” than earlier similar methods, takes expected timeO(nℝgn) and spaceO(n), and is eminently practical to implement. The analysis of the algorithm is also interesting in its own right and can serve as a model for many similar questions in both two and three dimensions. Finally we demonstrate how this approach for constructing Voronoi diagrams obviates the need for building a separate point-location structure for nearest-neighbor queries.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758770
    Library Location Call Number Volume/Issue/Year 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...