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
    Storing line segments in partition trees (1990)
    Springer
    BIT 30 (1990), S. 385-403 
    Details
    ISSN: 1572-9125
    Keywords: F 2.2 ; E 2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We design two variants of partition trees, calledsegment partition trees andinterval partition trees, that can be used for storing arbitrarily oriented line segments in the plane in an efficient way. The raw structures useO(n logn) andO(n) storage, respectively, and their construction time isO(n logn). In our applications we augment these structures by certain (simple) auxiliary structures, which may increase the storage and preprocessing time by a polylogarithmic factor. It is shown how to use these structures for solving line segment intersection queries, triangle stabbing queries and ray shooting queries in reasonably efficient ways. If we use the conjugation tree as the underlying partition tree, the query time for all problems isO(n λ), whereγ=log2(1+√5)−1≈0.695. The techniques are fairly simple and easy to understand.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01931656
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram (1987)
    Springer
    Algorithmica 2 (1987), S. 27-59 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Moving ladder ; Robotics ; Voronoi diagram ; Configuration space
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a collection of algorithms, all running in timeO(n 2 logn α (n) o(α(n)3)) for some fixed integers(where α(n) is the inverse Ackermann's function), for constructing a skeleton representation of a suitably generalized “Voronoi diagram” for a ladder moving in a two-dimensional space bounded by polygonal barriers consisting ofn line segments. This diagram, which is a two-dimensional subcomplex of the dimensional configuration space of the ladder, is introduced and analyzed in a companion paper by the present authors. The construction of the diagram described in this paper yields a motion-planning algorithm for the ladder which runs within the same time bound given above.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840348
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons (1987)
    Springer
    Algorithmica 2 (1987), S. 209-233 
    Details
    ISSN: 1432-0541
    Keywords: Triangulation ; Simple polygon ; Visibility ; Shortest paths ; Ray shooting ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840360
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Algorithms for bichromatic line-segment problems and polyhedral terrains (1994)
    Springer
    Algorithmica 11 (1994), S. 116-132 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Line-segment intersection ; Segment trees ; Lines in space ; Polyhedral terrains ; Deterministic and randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182771
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Planar geometric location problems (1994)
    Springer
    Algorithmica 11 (1994), S. 185-195 
    Details
    ISSN: 1432-0541
    Keywords: Facility location ; Parametric searching ; Duality ; Planar arrangements
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present anO(n 2 log3 n) algorithm for the two-center problem, in which we are given a setS ofn points in the plane and wish to find two closed disks whose union containsS so that the larger of the two radii is as small as possible. We also give anO(n 2 log5 n) algorithm for solving the two-line-center problem, where we want to find two strips that coverS whose maximum width is as small as possible. The best previous solutions of both problems requireO(n 3) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182774
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Randomized incremental construction of Delaunay and Voronoi diagrams (1992)
    Springer
    Algorithmica 7 (1992), S. 381-413 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Voronoi diagram ; randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give a new randomized incremental algorithm for the construction of planar Voronoi diagrams and Delaunay triangulations. The new algorithm is more “on-line” than earlier similar methods, takes expected timeO(nℝgn) and spaceO(n), and is eminently practical to implement. The analysis of the algorithm is also interesting in its own right and can serve as a model for many similar questions in both two and three dimensions. Finally we demonstrate how this approach for constructing Voronoi diagrams obviates the need for building a separate point-location structure for nearest-neighbor queries.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758770
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Finding effective “force targets” for two-dimensional, multifinger frictional grips (1992)
    Springer
    Algorithmica 8 (1992), S. 1-20 
    Details
    ISSN: 1432-0541
    Keywords: Robotics ; Grasp planning ; Robot control ; Computational Geometry ; Linear programming ; Parametric searching ; Davenport-Schinzel sequences
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we apply techniques from computational geometry to solve several problems in grasp planning and control in robotics. We consider the problem of calculating “force targets ” for a collection ofn fingers which grasp a two-dimensional object at known positions, at which the normals to the surface are also assumed to be known at least approximately. If the points at which the fingers touch the body do not allow apositive grip to be exerted (i.e., a grip in which the fingers hold the body in equilibrium by exerting friction-free forces in the directions of the corresponding inward-directed normals), it is appropriate to find the smallest coefficient of friction for which it is possible to assign a set of forces to be exerted by the fingers (so-calledfinger-force targets) which hold the object at equilibrium and such that each individual force lies within the corresponding cone of friction. We present an algorithm for this problem which runs in time0(n log2 n log logn). We also present another algorithm for preprocessing the given data so as to allow fast computation of the desired coefficient of friction for the case in which one needs to balance any given “query” external force and torque. Finally, we discuss simpler variants of our techniques which are likely to be more efficient when the problem is solved for a small number of fingers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758833
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Quasi-optimal upper bounds for simplex range searching and new zone theorems (1992)
    Springer
    Algorithmica 8 (1992), S. 407-429 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Range searching ; Space-time tradeoff
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ℜd so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n 〈m 〈n d ), then we show that it is possible to answer any query inO(n 1+ɛ/m 1/d ) query time afterO(m 1+ɛ) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n d+ɛ) storage for any fixed ɛ 〉 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758854
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Selecting distances in the plane (1993)
    Springer
    Algorithmica 9 (1993), S. 495-514 
    Details
    ISSN: 1432-0541
    Keywords: Parametric search ; Arrangements ; Random-sampling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a randomized algorithm for computing the kth smallest distance in a set ofn points in the plane, based on the parametric search technique of Megiddo [Mel]. The expected running time of our algorithm is O(n4/3 log8/3 n). The algorithm can also be made deterministic, using a more complicated technique, with only a slight increase in its running time. A much simpler deterministic version of our procedure runs in time O(n3/2 log5/2 n). All versions improve the previously best-known upper bound ofO(@#@ n9/5 log4/5 n) by Chazelle [Ch]. A simpleO(n logn)-time algorithm for computing an approximation of the median distance is also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187037
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles (1986)
    Springer
    Discrete & computational geometry 1 (1986), S. 59-71 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Let γ1,..., γ m bem simple Jordan curves in the plane, and letK 1,...,K m be their respective interior regions. It is shown that if each pair of curves γ i , γ j ,i ≠j, intersect one another in at most two points, then the boundary ofK=∩ i =1m K i contains at most max(2,6m − 12) intersection points of the curvesγ 1, and this bound cannot be improved. As a corollary, we obtain a similar upper bound for the number of points of local nonconvexity in the union ofm Minkowski sums of planar convex sets. Following a basic approach suggested by Lozano Perez and Wesley, this can be applied to planning a collision-free translational motion of a convex polygonB amidst several (convex) polygonal obstaclesA 1,...,A m . Assuming that the number of corners ofB is fixed, the algorithm presented here runs in timeO (n log2 n), wheren is the total number of corners of theA i 's.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187683
    Location Call Number Expected 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...