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
  • Arrangements of planes  (1)
  • Incremental  (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
    Incremental topological flipping works for regular triangulations (1996)
    Springer
    Algorithmica 15 (1996), S. 223-241 
    Details
    ISSN: 1432-0541
    Keywords: Geometric algorithms ; Grid generation ; Regular and Delaunay triangulations ; Flipping ; Topological order ; Point location ; Incremental ; Randomized
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A set ofn weighted points in general position in ℝ d defines a unique regular triangulation. This paper proves that if the points are added one by one, then flipping in a topological order will succeed in constructing this triangulation. If, in addition, the points are added in a random sequence and the history of the flips is used for locating the next point, then the algorithm takes expected time at mostO(nlogn+n [d/2]). Under the assumption that the points and weights are independently and identically distributed, the expected running time is between proportional to and a factor logn more than the expected size of the regular triangulation. The expectation is over choosing the points and over independent coin-flips performed by the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01975867
    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...