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
    Morphing Simple Polygons (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 1-34 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. In this paper we investigate the problem of morphing (i.e., continuously deforming) one simple polygon into another. We assume that our two initial polygons have the same number of sides n , and that corresponding sides are parallel. We show that a morph is always possible through an interpolating simple polygon whose n sides vary but stay parallel to those of the two original ones. If we consider a uniform scaling or translation of part of the polygon as an atomic morphing step, then we show that O(n log n) such steps are sufficient for the morph. Furthermore, the sequence of steps can be computed in O(n log n) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004540010017
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Ray shooting in polygons using geodesic triangulations (1994)
    Springer
    Algorithmica 12 (1994), S. 54-68 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray-shooting ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO(√ logn) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377183
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Lines in space: Combinatorics and algorithms (1996)
    Springer
    Algorithmica 15 (1996), S. 428-447 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Lines in space ; Plücker coordinates ; ε-Nets
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Questions about lines in space arise frequently as subproblems in three-dimensional computational geometry. In this paper we study a number of fundamental combinatorial and algorithmic problems involving arrangements ofn lines in three-dimensional space. Our main results include: 1. A tight Θ(n 2) bound on the maximum combinatorial description complexity of the set of all oriented lines that have specified orientations relative to then given lines. 2. A similar bound of Θ(n 3) for the complexity of the set of all lines passing above then given lines. 3. A preprocessing procedure usingO(n 2+ɛ) time and storage, for anyε〉0, that builds a structure supportingO(logn)-time queries for testing if a line lies above all the given lines. 4. An algorithm that tests the “towering property” inO(n 2+ɛ) time, for anyε〉0; don given red lines lie all aboven given blue lines? The tools used to obtain these and other results include Plücker coordinates for lines in space andε-nets for various geometric range spaces.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01955043
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Parallel computational geometry (1988)
    Springer
    Algorithmica 3 (1988), S. 293-327 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Data structures
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive data-structures for three-dimensional queries.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762120
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    A method for obtaining randomized algorithms with small tail probabilities (1996)
    Springer
    Algorithmica 16 (1996), S. 543-547 
    Details
    ISSN: 1432-0541
    Keywords: Las Vegas algorithms ; Randomized algorithm ; Tail probability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01940879
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    The number of edges of many faces in a line segment arrangement (1992)
    Springer
    Combinatorica 12 (1992), S. 261-274 
    Details
    ISSN: 1439-6912
    Keywords: 52 B 05 ; 52 C 10 ; 68 U 05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m 2/3 n 2/3+nα(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is Ω(m 2/3 n 2/3+nα(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m 2/3 t 1/3+nα(t/n)+nmin{logm,logt/n}), almost matching the lower bound of Ω(m 2/3 t 1/3+nα(t/n)) demonstrated in this paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01285815
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Long repetitive patterns in random sequences (1980)
    Springer
    Probability theory and related fields 53 (1980), S. 241-262 
    Details
    ISSN: 1432-2064
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Appearances of long repetitive sequences such as 00...0 or 1010...101 in random sequences are studied. The expected length of the longest repetitive run of any specified type in a random binary sequence of length n is shown to tend to the binary logarithm of n plus a periodic function of log n. Necessary and sufficient conditions are derived to ensure that with probability 1 an infinite random sequence should contain repetitive runs of specified lengths in given initial segments. Finally, the number of long repetitive runs of a specified kind that occur in a random sequence is studied. These results are derived from simple expressions for the generating functions for the probabilities of occurrences of various repetitive runs. These generating functions are rational, and lead to sharp asymptotic estimates for the probabilities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00531434
    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...