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
  • 1
    Electronic Resource
    Electronic Resource
    Storing line segments in partition trees (1990)
    Springer
    BIT 30 (1990), S. 385-403 
    Details
    ISSN: 1572-9125
    Keywords: F 2.2 ; E 2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We design two variants of partition trees, calledsegment partition trees andinterval partition trees, that can be used for storing arbitrarily oriented line segments in the plane in an efficient way. The raw structures useO(n logn) andO(n) storage, respectively, and their construction time isO(n logn). In our applications we augment these structures by certain (simple) auxiliary structures, which may increase the storage and preprocessing time by a polylogarithmic factor. It is shown how to use these structures for solving line segment intersection queries, triangle stabbing queries and ray shooting queries in reasonably efficient ways. If we use the conjugation tree as the underlying partition tree, the query time for all problems isO(n λ), whereγ=log2(1+√5)−1≈0.695. The techniques are fairly simple and easy to understand.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01931656
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Planar geometric location problems (1994)
    Springer
    Algorithmica 11 (1994), S. 185-195 
    Details
    ISSN: 1432-0541
    Keywords: Facility location ; Parametric searching ; Duality ; Planar arrangements
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present anO(n 2 log3 n) algorithm for the two-center problem, in which we are given a setS ofn points in the plane and wish to find two closed disks whose union containsS so that the larger of the two radii is as small as possible. We also give anO(n 2 log5 n) algorithm for solving the two-line-center problem, where we want to find two strips that coverS whose maximum width is as small as possible. The best previous solutions of both problems requireO(n 3) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182774
    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...