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
Filter
  • 68 U 05  (1)
  • Arrangements of planes  (1)
  • Power diagrams  (1)
  • 1
    Electronic Resource
    Electronic Resource
    Edge-skeletons in arrangements with applications (1986)
    Springer
    Algorithmica 1 (1986), S. 93-109 
    Details
    ISSN: 1432-0541
    Keywords: Arrangements of planes ; Power diagrams ; Computational geometry ; Asymptotic complexity ; Dynamic data structures ; Perturbation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE 2 and space cutting trees inE 3. We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840438
    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...