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
    Translation separability of sets of polygons (1987)
    Springer
    The visual computer 3 (1987), S. 227-235 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Data structures ; Motion problems ; Separability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider the problem of separating a set of polygons by a sequence of translations (one such collision-free translation motion for each polygon). If all translations are performed in a common direction the separability problem so obtained has been referred to as the uni-directional separability problem; for different translation directions, the more general multi-directional separability problem arises. The class of such separability problems has been studied previously and arises e.g. in computer graphics and robotics. Existing solutions to the uni-directional problem typically assume the objects to have a certain predetermined shape (e.g., rectangular or convex objects), or to have a direction of separation already available. Here we show how to compute all directions of unidirectional separability for sets of arbitrary simple polygons. The problem of determining whether a set of polygons is multi-directionally separable had been posed by G.T. Toussaint. Here we present an algorithm for solving this problem which, in addition to detecting whether or not the given set is multidirectionally separable, also provides an ordering in which to separate the polygons. In case that the entire set is not multi-directionally separable, the algorithm will find the largest separable subset.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01952829
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Solving visibility and separability problems on a mesh-of-processors (1988)
    Springer
    The visual computer 3 (1988), S. 356-370 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Mesh-of-Processors ; Parallel algorithms ; Separability-Visibility
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms: - AnO( $$\sqrt N$$ time algorithm for computing on a Mesh-of-Processors of size N the visibility polygon from a point located in anN-vertex polygon, possibly with holes. -O( $$\sqrt N$$ ) time algorithms for computing on a Mesh-of-Processors of sizeN the set of all points on the boundary of anN-vertex polygonP which are visible in a given directiond as well as the visibility hull ofP for a given directiond. - AnO( $$\sqrt N$$ ) time algorithm for detecting on a Mesh-of-Processors of size 2N whether twoN-vertex polygons are separable in a given direction and anO( $$\sqrt {MN}$$ ) time algorithm for detecting on a Mesh-of-Processors of sizeMN whetherM N-vertex polygons are sequentially separable in a given direction. All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901193
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Optical clustering (1986)
    Springer
    The visual computer 2 (1986), S. 39-43 
    Details
    ISSN: 1432-2315
    Keywords: Clustering methods ; Computational geometry ; Picture analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper presents a definition of ‘optical clusters’ which is derived from the concept of optical resolution. The clustering problem (induced by this definition) is transformed such that the application of well known Computational Geometry methods yields efficient solutions. One result (which can be extended to different classes of objects and metrices) is the following: Given a setS ofN disjoint line segments inE 2. (a) The optical clusters with respect to a given separation parameterr∈R can be computed in timeO(Nlog2 N). (b) Given an interval [a, b] for the numberm(S, r) of optical clusters which we want to compute, then timeO(N log2 N)[O(Nlog2 N+CN)] suffices to compute the interval [R(b),R(a)]={r∈R/m(S,r)∈[a,b]} [allC optical clusterings withR(b)≦ r≦R(a)].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01890986
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Editor's foreword special issue on parallel algorithms for geometric problems on digitized pictures (1991)
    Springer
    Algorithmica 6 (1991), S. 621-623 
    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/BF01759064
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Optimal visibility algorithms for binary images on the hypercube (1990)
    Springer
    International journal of parallel programming 19 (1990), S. 213-224 
    Details
    ISSN: 1573-7640
    Keywords: Hypercube Algorithms ; Image Processing ; Parallel Algorithms ; Visibility
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Consider an×n binary image. Given a directionD, the parallel visibility problem consists of determining for each pixel of the image the portion that is visible (i.e., not obstructed by any other black pixel of the image) in directionD from infinity. A related problem, referred to as point visibility, is to compute for each pixel the portion that is visible from a given pointp. In this paper, we deriveO(logn) time SIMD algorithms for each of these two problems on the hypercube, where one processor is assigned to every pixel of the image. Since the worst case communication distance of two processors in an 2-processor hypercube is 2 logn, it follows that both of the above algorithms are asymptotically optimal.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01407955
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Pipelined search on coarse grained networks (1989)
    Springer
    International journal of parallel programming 18 (1989), S. 359-364 
    Details
    ISSN: 1573-7640
    Keywords: Average-case analysis ; coarse grained processor network ; parallel algorithms ; pipelining ; searching
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The time complexity of searching a sorted list ofn elements in parallel on a coarse grained network of diameterD and consisting ofN processors (wheren may be much larger thanN) is studied. The worst case period and latency of a sequence of pipeline search operation are easity seen to be Ω(logn−logN) and Ω(D+logn−logN), respectively. Since forn=N 1+Ω(1) the worst-case period is Ω(logn) (which can be achieved by a single processor), coarse-grained networks appear to be unsuitable for the search problem. By contrast, it is demonstrated using standard queuing theory techniques that a constant expected period can be achieved provided thatn=O(N2 N ).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01379185
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Optical clustering on a mesh-connected computer (1991)
    Springer
    International journal of parallel programming 20 (1991), S. 475-486 
    Details
    ISSN: 1573-7640
    Keywords: Mesh-connected computer ; optical clustering ; image processing ; computational geometry ; connected components
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper, we present optimal parallel algorithms for optical clustering on a mesh-connected computer.Optical clustering is a clustering technique based on the principal of optical resolution, and is of particular interest in picture analysis. The algorithms we present are based on the application of parallel algorithms in computational geometry and graph theory. In particular, we show that given a setS ofN points in the Euclidean plane, the following problems can be solved in optimal $$O\left( {\sqrt N } \right)$$ time on a mesh-connected computer of sizeN. 1. Determine the optical clusters ofS with respect to a given separation parameter. 2. Given an interval [a, b] representing the number of optical clusters desired in the clustering ofS, determine the range of the separation parameter that will result in such an optical clustering.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01547896
    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...