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
    Dynamic half-space range reporting and its applications (1995)
    Springer
    Algorithmica 13 (1995), S. 325-345 
    Details
    ISSN: 1432-0541
    Keywords: Arrangements ; Cuttings ; Range-searching ; Dynamization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the half-space range-reporting problem: Given a setS ofn points in ℝd, preprocess it into a data structure, so that, given a query half-space γ, allk points ofS ∩ γ can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points ofS. For a given parameterm,n ≤m ≤n ⌊d/2⌋ and an arbitrarily small positive constant ɛ, we achieveO(m 1+ɛ) space and preprocessing time, O((n/m ⌊d/2⌋ logn+k) query time, and O(m1+ɛn) amortized update time (d ≳ 3). We present, among others, the following applications: an O(n1+ɛ)-time algorithm for computing convex layers in ℝ3, and an output sensitive algorithm for computing a level in an arrangements of planes in ℝ3, whose time complexity is O((b+n) nɛ, whereb is the size of the level.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293483
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Connected component and simple polygon intersection searching (1996)
    Springer
    Algorithmica 15 (1996), S. 626-660 
    Details
    ISSN: 1432-0541
    Keywords: Arrangements ; Data structures ; Intersection searching ; Partition trees
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Efficient data structures are given for the following two query problems: (i) preprocess a setP of simple polygons with a total ofn edges, so that all polygons ofP intersected by a query segment can be reported efficiently, and (ii) preprocess a setS ofn segments, so that the connected components of the arrangement ofS intersected by a query segment can be reported quickly. In these problems we do not want to return the polygons or connected components explicitly (i.e., we do not wish to report the segments defining the polygon, or the segments lying in the connected components). Instead, we assume that the polygons (or connected components) are labeled and we just want to report their labels. We present data structures of sizeO(n 1+ε) that can answer a query in timeO(n 1+ε+k), wherek is the output size. If the edges ofP (or the segments inS) are orthogonal, the query time can be improved toO(logn+k) usingO(n logn) space. We also present data structures that can maintain the connected components as we insert new segments. For arbitrary segments the amortized update and query time areO(n 1/2+ε) andO(n 1/2+ε+k), respectively, and the space used by the data structure isO(n 1+ε. If we allowO(n 4/3+ε space, the amortized update and query time can be improved toO(n 1/3+ε andO(n 1/3+ε+k, respectively. For orthogonal segments the amortized update and query time areO(log2 n) andO(log2 n+klogn), and the space used by the data structure isO (n logn). Some other related results are also mentioned.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01940884
    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...