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
    Algorithms for bichromatic line-segment problems and polyhedral terrains (1994)
    Springer
    Algorithmica 11 (1994), S. 116-132 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Line-segment intersection ; Segment trees ; Lines in space ; Polyhedral terrains ; Deterministic and randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182771
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    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
  • 5
    Electronic Resource
    Electronic Resource
    Finding extrema with unary predicates (1993)
    Springer
    Algorithmica 9 (1993), S. 591-600 
    Details
    ISSN: 1432-0541
    Keywords: Adversary argument ; Algorithms ; Communication complexity ; Lower bounds ; Maximum finding ; Threshold predicates ; Unary predicates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the problem of determining the maximum and minimum elements of a setX={x1...,x n }, drawn from some finite universeU of real numbers, using only unary predicates of the inputs. It is shown that θ(n+ log¦U¦) unary predicate evaluations are necessary and sufficient, in the worst case. Results are applied to (i) the problem of determining approximate extrema of a set of real numbers, in the same model, and (ii) the multiparty broadcast communication complexity of determining the extrema of an arbitrary set of numbers held by distinct processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190157
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    A linear-time algorithm for computing the voronoi diagram of a convex polygon (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 591-604 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram ofn sites in the plane can be computed in Θ(n) time when these sites form the vertices of a convex polygon in, say, counterclockwise order. This settles an open problem in computational geometry. Our techniques can also be used to obtain linear-time algorithms for computing the furthest-site Voronoi diagram and the medial axis of a convex polygon and for deleting a site from a general planar Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187749
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Visibility and intersection problems in plane geometry (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 551-581 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We develop new data structures for solving various visibility and intersection problems about a simple polygonP onn vertices. Among our results are a simpleO(n logn)-time algorithm for computing the illuminated subpolygon ofP from a luminous side, and anO(logn)-time algorithm for determining which side ofP is first hit by a bullet fired from a point in a certain direction. The latter method requires preprocessing onP which takes timeO(n logn) and spaceO(n). The two main tools in attacking these problems are geometric duality on the two-sided plane and fractional cascading.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187747
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    The complexity of cutting complexes (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 139-181 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187720
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    The upper envelope of piecewise linear functions: Algorithms and applications (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 311-336 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper studies applications of envelopes of piecewise linear functions to problems in computational geometry. Among these applications we find problems involving hidden line/surface elimination, motion planning, transversals of polytopes, and a new type of Voronoi diagram for clusters of points. All results are either combinatorial or computational in nature. They are based on the combinatorial analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm for computing envelopes described in this paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187733
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    On the general motion-planning problem with two degrees of freedom (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 491-521 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that, under reasonable assumptions, any collision-avoiding motion-planning problem for a moving system with two degrees of freedom can be solved in timeO(λ s (n) log2 n), wheren is the number of collision constraints imposed on the system,s is a fixed parameter depending, e.g., on the maximum algebraic degree of these constraints, andλ s (n) is the (almost linear) maximum length of (n, s) Davenport-Schinzel sequences. This follows from an upper bound ofO(λ s (n)) that we establish for the combinatorial complexity of a single connected component of the space of all free placements of the moving system. Although our study is motivated by motion planning, it is actually a study of topological, combinatorial, and algorithmic issues involving a single face in an arrangement of curves. Our results thus extend beyond the area of motion planning, and have applications in many other areas.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187744
    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...