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
    Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams (1997)
    Springer
    Discrete & computational geometry 18 (1997), S. 433-454 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E 4 . Our algorithm runs in $O((n+f)\log^2 f)$ time and uses O(n+f) space. This is the first algorithm within a polylogarithmic factor of optimal $O(n \log f + f)$ time over the whole range of f. By a standard lifting map, we obtain output-sensitive algorithms for the Voronoi diagram or Delaunay triangulation in E 3 and for the portion of a Voronoi diagram that is clipped to a convex polytope. Our approach simplifies the ``ultimate convex hull algorithm'' of Kirkpatrick and Seidel in E 2 and also leads to improved output-sensitive results on constructing convex hulls in E d for any even constant d 〉 4.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009327
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Quantitative Steinitz's theorems with applications to multifingered grasping (1992)
    Springer
    Discrete & computational geometry 7 (1992), S. 295-318 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We prove the following quantitative form of a classical theorem of Steintiz: Letm be sufficiently large. If the convex hull of a subsetS of Euclideand-space contains a unit ball centered on the origin, then there is a subset ofS with at mostm points whose convex hull contains a solid ball also centered on the origin and havingresidual radius $$1 - 3d\left( {\frac{{2d^2 }}{m}} \right)^{2/(d - 1)} .$$ The casem=2d was first considered by Bárányet al. [1]. We also show an upper bound on the achievable radius: the residual radius must be less than $$1 - \frac{1}{{17}}\left( {\frac{{2d^2 }}{m}} \right)^{2/(d - 1)} .$$ These results have applications in the problem of computing the so-calledclosure grasps by anm-fingered robot hand. The above quantitative form of Steinitz's theorem gives a notion ofefficiency for closure grasps. The theorem also gives rise to some new problems in computational geometry. We present some efficient algorithms for these problems, especially in the two-dimensional case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187843
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Editor's foreword (1989)
    Springer
    Algorithmica 4 (1989), S. 1-2 
    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/BF01553876
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Parallel triangulation of a polygon in two calls to the trapezoidal map (1988)
    Springer
    Algorithmica 3 (1988), S. 279-288 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithm ; Triangulation ; Polygon
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best-known trapezoidal map algorithm, ours run in timeO(logn) usingO(n) CREW PRAM processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762118
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Preface special issue on robotics (1987)
    Springer
    Algorithmica 2 (1987), S. 363-365 
    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/BF01840367
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    On-line motion planning: Case of a planar rod (1991)
    Springer
    Annals of mathematics and artificial intelligence 3 (1991), S. 1-20 
    Details
    ISSN: 1573-7470
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we develop an algorithm for planning the motion of a planar “rod” (a line segment) amidst obstacles bounded by simple, closed polygons. The exact shape, number and location of the obstacles are assumed unknown to the planning algorithm, which can only obtain information about the obstacles by detecting points of contact with the obstacles. The ability to detect contact with obstacles is formalized by move primitives that we callguarded moves. We call ours theon-line motion planning problem as opposed to the usualoff-line version. This is a significant departure from the usual setting for motion planning problems. What we demonstrate is that the retraction method can be applied, although new issues arise that have no counterparts in the usual setting. We are able to obtain an algorithm with path complexityO(n 2) guarded moves, wheren is the number of obstacle corners. This matches the known lower bound. The computational complexityO(n 2logn) of our algorithm matches the best known algorithm for the off-line version.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01530886
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Book
    Book
    Fundamental problems of algorithmic algebra (2000)
    Oxford u.a. :Oxford University Pr.,
    Details
    Title: Fundamental problems of algorithmic algebra
    Author: Yap, Chee Keng
    Publisher: Oxford u.a. :Oxford University Pr.,
    Year of publication: 2000
    Pages: 528 S.
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...