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
Filter
  • Computational geometry  (3)
  • Duality  (1)
  • 1
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    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
  • 4
    Electronic Resource
    Electronic Resource
    Quasi-optimal upper bounds for simplex range searching and new zone theorems (1992)
    Springer
    Algorithmica 8 (1992), S. 407-429 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Range searching ; Space-time tradeoff
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ℜd so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n 〈m 〈n d ), then we show that it is possible to answer any query inO(n 1+ɛ/m 1/d ) query time afterO(m 1+ɛ) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n d+ɛ) storage for any fixed ɛ 〉 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758854
    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...