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: 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
  • 2
    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
  • 3
    Electronic Resource
    Electronic Resource
    Constructing strongly convex approximate hulls with inaccurate primitives (1993)
    Springer
    Algorithmica 9 (1993), S. 534-560 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Epsilon Geometry ; Approximate computations ; Robust algorithms ; Strongly convex polygons ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The first half of this paper introducesEpsilon Geometry, a framework for the development of robust geometric algorithms using inaccurate primitives. Epsilon Geometry is based on a very general model of imprecise computations, which includes floating-point and rounded-integer arithmetic as special cases. The second half of the paper introduces the notion of a (−ɛ)-convex polygon, a polygon that remains convex even if its vertices are all arbitrarily displaced by a distance ofɛ of less, and proves some interesting properties of such polygons. In particular, we prove that for every point set there exists a (−ɛ)-convex polygonH such that every point is at most 4ɛ away fromH. Using the tools of Epsilon Geometry, we develop robust algorithms for testing whether a polygon is (−ɛ)-convex, for testing whether a point is inside a (−ɛ)-convex polygon, and for computing a (−ɛ)-convex approximate hull for a set of points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190154
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    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
  • 5
    Electronic Resource
    Electronic Resource
    Visibility of disjoint polygons (1986)
    Springer
    Algorithmica 1 (1986), S. 49-63 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Computer graphics ; Robotics ; Visibility ; Hidden-line Elimination ; Visibility graph ; Shortest path
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n 2) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n 2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n 2) time, improving earlierO(n 2 logn) results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840436
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    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
  • 7
    Electronic Resource
    Electronic Resource
    Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons (1987)
    Springer
    Algorithmica 2 (1987), S. 209-233 
    Details
    ISSN: 1432-0541
    Keywords: Triangulation ; Simple polygon ; Visibility ; Shortest paths ; Ray shooting ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840360
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    An efficient algorithm for finding the CSG representation of a simple polygon (1993)
    Springer
    Algorithmica 10 (1993), S. 1-23 
    Details
    ISSN: 1432-0541
    Keywords: Constructive solid geometry ; Computational geometry ; Boundary representation ; Monotone boolean formulae ; Incremental convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior only implicitly, and constructive solid geometry representations, which model a complex object, surface and interior together, as a boolean combination of simpler objects. Because neither representation is good for all applications, conversion between the two is often necessary. We consider the problem of converting boundary representations of polyhedral objects into constructive solid geometry (CSG) representations. The CSG representations for a polyhedronP are based on the half-spaces supporting the faces ofP. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practicalO(n logn) algorithm for doing this boundary-to-CSG conversion for a simple polygon ofn sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01908629
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    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
  • 10
    Electronic Resource
    Electronic Resource
    On arrangements of Jordan arcs with three intersections per pair (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 523-539 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only Θ(nα(n)), whereα(n) is the extremely slowly growing functional inverse of Ackermann's function.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187745
    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...