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
    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
  • 2
    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
  • 3
    Electronic Resource
    Electronic Resource
    Cellular immune response of patients with uveitis to peptide M, a retinal S-antigen fragment (1993)
    Springer
    Journal of clinical immunology 13 (1993), S. 352-358 
    Details
    ISSN: 1573-2592
    Keywords: Lymphocyte proliferation assay ; peptide M ; yeast histone H3 ; retinal S-antigen ; uveitis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Medicine
    Notes: Abstract Peptide M, an 18-amino acid fragment from position 303 to position 320 of retinal S-antigen, produces experimental autoimmune uveitis (EAU), similar to that produced by native S-antigen, in several vertebrate species including nonhuman primates. It was observed that 12 of the 39 (30.7%) patients with uveitis, 1 of the 29 (3.4%) patients with systemic connective tissue disorders (CTD) without eye involvement, 2 of the 7 (5.8%) patients of CTD with uveitis, 1 of the 17 (5.8%) patients with diabetic retinopathy, and none of the 19 normal healthy controls showed a significant lymphoproliferative response to peptide M (stimulation index of 3 or more). Yeast histone H3 peptide gave a positive response in 1 (2.5%), 2 (6.8%), 1 (14.2%), 2 (11.7%), and 2 (10.5%) individuals, respectively, in the different groups studied. In a few cases a positive response to yeast histone H3 peptide was observed without significant stimulation to peptide M. These findings indicate that peptide M could also be an immunogenic epitope of S-antigen in humans and be aetiopathologically related to uveitis in a subset of patients with this disease. However, unlike experimental animals, the responses to peptide M and yeast histone H3 were nonconcordant, necessitating further studies.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00920244
    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...