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
    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
  • 2
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...