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
    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
  • 3
    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
  • 4
    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
  • 5
    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
  • 6
    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
  • 7
    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
  • 8
    Electronic Resource
    Electronic Resource
    The complexity of many cells in arrangements of planes and related problems (1990)
    Springer
    Discrete & computational geometry 5 (1990), S. 197-216 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5−δ n 4/5+2δ +m+n logm), for anyδ〉0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m 3/4−δ n 3/4+3δ +m) log2 n+n logn logm) for anyδ〉0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m 3/4−δ n 3/4+3δ +m] log2 n+n logn logm) for anyδ〉0. (v) The maximum number of facets (i.e., (d−1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d〉3, isO(m 2/3 n d/3 logn+n d−1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187785
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    On the zone of a surface in a hyperplane arrangement (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 177-186 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetH be a collection ofn hyperplanes in ℝ d , letA denote the arrangement ofH, and let σ be a (d−1)-dimensional algebraic surface of low degree, or the boundary of a convex set in ℝ d . Thezone of σ inA is the collection of cells ofA crossed by σ. We show that the total number of faces bounding the cells of the zone of σ isO(n d−1 logn). More generally, if σ has dimensionp, 0≤p〈d, this quantity isO(n [(d+p)/2]) ford−p even andO(n [(d+p)/2] logn) ford−p odd. These bounds are tight within a logarithmic factor.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189317
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    The upper envelope of voronoi surfaces and its applications (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 267-291 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a setS ofsources (points or segments) in ℜ211C;d, we consider the surface in ℜ211C; d+1 that is the graph of the functiond(x)=min pεS ρ(x, p) for some metricρ. This surface is closely related to the Voronoi diagram, Vor(S), ofS under the metricρ. The upper envelope of a set of theseVoronoi surfaces, each defined for a different set of sources, can be used to solve the problem of finding the minimum Hausdorff distance between two sets of points or line segments under translation. We derive bounds on the number of vertices on the upper envelope of a collection of Voronoi surfaces, and provide efficient algorithms to calculate these vertices. We then discuss applications of the methods to the problems of finding the minimum Hausdorff distance under translation, between sets of points and segments.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189323
    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...