ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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
    An efficient algorithm for maxdominance, with applications (1989)
    Springer
    Algorithmica 4 (1989), S. 221-236 
    Details
    ISSN: 1432-0541
    Keywords: Analysis of algorithms ; Computational geometry ; Tree computations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a planar setS ofn points,maxdominance problems consist of computing, for everyp εS, some function of the maxima of the subset ofS that is dominated byp. A number of geometric and graph-theoretic problems can be formulated as maxdominance problems, including the problem of computing a minimum independent dominating set in a permutation graph, the related problem of finding the shortest maximal increasing subsequence, the problem of enumerating restricted empty rectangles, and the related problem of computing the largest empty rectangle. We give an algorithm for optimally solving a class of maxdominance problems. A straightforward application of our algorithm yields improved time bounds for the above-mentioned problems. The techniques used in the algorithm are of independent interest, and include a linear-time tree computation that is likely to arise in other contexts.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553888
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Editor's foreword special issue on the sixth annual symposium on computational geometry (1992)
    Springer
    Algorithmica 8 (1992), S. 343-344 
    Details
    ISSN: 1432-0541
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758850
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A faster parallel algorithm for a matrix searching problem (1993)
    Springer
    Algorithmica 9 (1993), S. 156-167 
    Details
    ISSN: 1432-0541
    Keywords: Algorithms ; Parallel computation ; Monotone matrices
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give an improved parallel algorithm for the problem of computing the tube minima of a totally monotonen ×n ×n matrix, an important matrix searching problem that was formalized by Aggarwal and Park and has many applications. Our algorithm runs inO(log logn) time withO(n2/log logn) processors in theCRCW-PRAM model, whereas the previous best ran inO((log logn)2) time withO(n2/(log logn)2 processors, also in theCRCW-PRAM model. Thus we improve the speed without any deterioration in thetime ×processors product. Our improved bound immediately translates into improvedCRCW-PRAM bounds for the numerous applications of this problem, including string editing, construction of Huffmann codes and other coding trees, and many other combinatorial and geometric problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188710
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Parallel algorithms for some functions of two convex polygons (1988)
    Springer
    Algorithmica 3 (1988), S. 535-548 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Convex polygons ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Let P andQ be two convex,n-vertex polygons. We consider the problem of computing, in parallel, some functions ofP andQ whenP andQ are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM havingn 1/k processors can compute the following functions in O(k1+ɛ) time: (i) the common tangents betweenP andQ, and (ii) the distance betweenP andQ (and hence a straight line separating them). The positive constant ɛ can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762130
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Topological numbering of features on a mesh (1991)
    Springer
    Algorithmica 6 (1991), S. 762-769 
    Details
    ISSN: 1432-0541
    Keywords: Image processing ; Mesh-connected processor array ; Parallel computation ; Stereo matching ; Topological sorting ; Tree computation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Assume we are given ann ×n binary image containing horizontally convex features; i.e., for each feature, each of its row's pixels form an interval on that row. In this paper we consider the problem of assigning topological numbers to such features, i.e., assign a number to every featuref so that all features to the left off in the image have a smaller number assigned to them. This problem arises in solutions to the stereo matching problem. We present a parallel algorithm to solve the topological numbering problem inO(n) time on ann ×n mesh of processors. The key idea of our solution is to create a tree from which the topological numbers can be obtained even though the tree does not uniquely represent the “to the left of” relationship of the features.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759070
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    On the parallel-decomposability of geometric problems (1992)
    Springer
    Algorithmica 8 (1992), S. 209-231 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Mesh-connected arrays of processors ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n 1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen 〉p. The goal we seek is to achieve, when solving a problem of sizen 〉p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen 〉p as when solving a problem of sizep.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758844
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Checking similarity of planar figures (1984)
    Springer
    International journal of parallel programming 13 (1984), S. 279-290 
    Details
    ISSN: 1573-7640
    Keywords: Analysis of algorithms ; computational geometry ; string pattern matching
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Two planar figures aresimilar if a scaled version of one of them can be moved so that it coincides with the second figure. The problem of checking whether two planar figures are similar is relevant to both computational geometry and pattern recognition. An efficient algorithm is known for checking whether two polygonsP andQ are similar(1) The purpose of this note is to give an efficient algorithm for checking whether two planar figuresP andQ are similar when the figures are no longer constrained to be polygons. We give anO(n logn) time algorithm for solving this problem when each figure consists of a collection of (possibly intersecting) straight line segments, circles, and ellipses. Our algorithm can easily be modified for figures which include other geometric patterns as well. We also prove that our algorithm is optimal.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00977833
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    facet.materialart.
    Unknown
    Computing some distance functions between polygons (1991)
    Elsevier
    Details
    Publication Date: 1991-01-01
    Print ISSN: 0031-3203
    Electronic ISSN: 1873-5142
    Topics: Computer Science
    Published by Elsevier
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    PAPER CURRENT
  • 9
    facet.materialart.
    Unknown
    On the parallel-decomposability of geometric problems (1992)
    Springer
    Details
    Publication Date: 1992-12-01
    Print ISSN: 0178-4617
    Electronic ISSN: 1432-0541
    Topics: Computer Science , Mathematics
    Published by Springer
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    PAPER CURRENT
  • 10
    facet.materialart.
    Unknown
    Topological numbering of features on a mesh (1991)
    Springer
    Details
    Publication Date: 1991-06-01
    Print ISSN: 0178-4617
    Electronic ISSN: 1432-0541
    Topics: Computer Science , Mathematics
    Published by Springer
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    PAPER CURRENT
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...