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
    Springer
    Algorithmica 1 (1986), S. 163-191 
    ISSN: 1432-0541
    Keywords: Fractional cascading ; Iterative search ; Multiple look-up ; Binary search ; B-tree ; Iterative search ; Multiple look-up ; Range query ; Dynamization of data structures
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents several applications offractional cascading, a new searching technique which has been described in a companion paper. The applications center around a variety of geometric query problems. Examples include intersecting a polygonal path with a line, slanted range search, orthogonal range search, computing locus functions, and others. Some results on the optimality of fractional cascading, and certain extensions of the technique for retrieving additional information are also included.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 15 (1996), S. 481-494 
    ISSN: 1432-0541
    Keywords: Design and analysis of algorithms ; Combinatorics on strings ; Pattern matching ; Substring statistics ; Suffix tree ; Augmented suffix tree ; Period of a string ; Repetition in a string
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a textstringx of lengthn, theMinimal Augmented Suffix Tree T (x) ofx is a digital-search index that returns, for anyquery stringw and in a number of comparisons bounded by the length ofw, the maximum number of nonoverlapping occurrences ofw inx. It is shown that, denoting the length ofx byn, T(x) can be built in timeO(n log2 n) and spaceO(n logn), off-line on a RAM.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 3
    ISSN: 1432-0541
    Keywords: Path planning ; Robotics ; Mobile robots ; Controllability ; Nonholonomy ; Optimal maneuvering ; Collision avoidance
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider mobile robots made of a single body (car-like robots) or several bodies (tractors towing several trailers sequentially hooked). These robots are known to be nonholonomic, i.e., they are subject to nonintegrable equality kinematic constraints involving the velocity. In other words, the number of controls (dimension of the admissible velocity space), is smaller than the dimension of the configuration space. In addition, the range of possible controls is usually further constrained by inequality constraints due to mechanical stops in the steering mechanism of the tractor. We first analyze the controllability of such nonholonomic multibody robots. We show that the well-known Controllability Rank Condition Theorem is applicable to these robots even when there are inequality constraints on the velocity, in addition to the equality constraints. This allows us to subsume and generalize several controllability results recently published in the Robotics literature concerning nonholonomic mobile robots, and to infer several new important results. We then describe an implemented planner inspired by these results. We give experimental results obtained with this planner that illustrate the theoretical results previously developed.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 10 (1993), S. 182-200 
    ISSN: 1432-0541
    Keywords: Motion planning ; Ulam's problem ; Optimal motion ; Cauchy's surface-area formula
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the problem of shortest paths for a line segment in the plane. As a measure of the distance traversed by a path, we take the average curve length of the orbits of prescribed points on the line segment. This problem is nontrivial even in free space (i.e., in the absence of obstacles). We characterize all shortest paths of the line segment moving in free space under the measured 2, the average orbit length of the two endpoints. The problem ofd 2 optimal motion has been solved by Gurevich and also by Dubovitskij, who calls it Ulam's problem. Unlike previous solutions, our basic tool is Cauchy's surface-area formula. This new approach is relatively elementary, and yields new insights.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 10 (1993), S. 201-225 
    ISSN: 1432-0541
    Keywords: Robotics ; Parts feeding ; Planning ; Grasping ; Compliance ; Motion planning with uncertainty ; Compliant motion planning
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In manufacturing it is often necessary to orient parts prior to packing or assembly. We say that a planar part ispolygonal if its convex hull is a polygon. We consider the following problem: given a list ofn vertices describing a polygonal part whose initial orientation is unknown, find the shortest sequence of mechanical gripper actions that is guaranteed to orient the part up to symmetry in its convex hull. We show that such a sequence exists for any polygonal part by giving anO[n 2 logn) algorithm for finding the sequence. Since the gripper actions do not require feedback, this result implies that any polygonal part can be orientedwithout sensors.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 16 (1996), S. 4-32 
    ISSN: 1432-0541
    Keywords: Graph drawing ; Canonical ordering ; Linear time ; Convex ; Orthogonal ; Visibility representation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows: Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices. Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn〉6, then every edge has at most two bends. Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid. Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 7
    ISSN: 1432-0541
    Keywords: Parts orienting ; Part sorters ; Manipulation ; Material handling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The positioning and orienting of parts is a standard problem in manufacturing. Orienting parts is often a prelude to the assembly of parts at tight tolerances. This paper considers the problem of orienting a part resting on a table, by tilting the table. The initial orientation of the part is assumed to be completely unknown. The objective is to tilt the table in a manner that reduces the uncertainty in the part's orientation. This paper focuses on three-dimensional polyhedral parts, with infinite friction between the parts and the table, and for which all transitions between different face-table contacts may be regarded as rotations across edges. The paper proposes a planner that determines a sequence of tilting operations designed to minimize the uncertainty in the part's orientation. The planner runs in timeO(n 3), wheren is the number of faces of the polyhedron. The planner produces a sequence ofO(n) distinct tilting operations. Each tilting operation wobbles the table until the part is in steady state.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 10 (1993), S. 292-352 
    ISSN: 1432-0541
    Keywords: Simulation ; Dynamics ; Friction ; Optimization ; Configuration space ; Robotics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In rigid-body simulation it is necessary to compute the forces that arise between contacting bodies to prevent interpenetration. This paper studies the problem of rigid-body simulation when the bodies being simulated are restricted to contact at only finitely many points. Some theoretical and practical issues in computing contact forces for systems with large numbers of contact points are considered. Both systems of rigid bodies with and without Coulomb friction are studied. Complexity results are derived for certain classes of configurations and numerical methods for computing contact forces are discussed.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 9
    ISSN: 1432-0541
    Keywords: Uncertainty ; Robotics ; Randomization ; Probabilistic algorithms ; Automatic programming ; Planning with uncertainty
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper explores the use of randomization as a primitive action in the solution of robot tasks. An example of randomization is the strategy of shaking a bin containing a part in order to orient the part in a desired stable state with some high probability. Further examples include tapping, vibrating, twirling, and random search. For instance, it is sometimes beneficial for a system to execute random motions purposefully when the precise motions required to perform an operation are unknown, as when they lie below the available sensor resolution. The purpose of this paper is to provide a theoretical framework for the planning and execution of randomized strategies for robot tasks. This framework is built on the standard backchaining approach of dynamic programming. Specifically, a randomizing planner backchains from the goal in a state space whose states describe the knowledge available to the system at run-time. By choosing random actions in a principled manner at run-time, a system can sometimes obtain a probabilistic strategy for accomplishing a task even when no guaranteed strategy exists for accomplishing that task. In other cases, the system may be able to obtain a speedup over an existing guaranteed strategy. The main result of this paper consists of two examples. One example shows that randomization can sometimes speed up task completion from exponential time to polynomial time. The other example shows that such a speedup is not always possible.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 10 (1993), S. 353-364 
    ISSN: 1432-0541
    Keywords: Approximate string matching ; Edit distance ; Dynamic programming ; Suffix automaton ; Aho-Corasick automaton
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Theapproximate string matching problem is, given a text string, a pattern string, and an integerk, to find in the text all approximate occurrences of the pattern. An approximate occurrence means a substring of the text with edit distance at mostk from the pattern. We give a newO(kn) algorithm for this problem, wheren is the length of the text. The algorithm is based on the suffix automaton with failure transitions and on the diagonalwise monotonicity of the edit distance table. Some experiments showing that the algorithm has a small overhead are reported.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...