Probabilistic road-map (PRM) planners have shown great promise in attacking previously infeasible motion planning problems with many degrees of freedom. Yet when such a planner fails to find a path, it is not clear that no path exists, or that the planner simply did not sample adequately or intelligently the free part of the configuration space. We propose to attack the motion planning problem from the other end, focusing on disconnection proofs, or proofs showing that there exists no solution to the posed motion planning problem. Just as PRM planners avoid generating a complete description of the configuration space, our disconnection provers search for certain special classes of proofs that are compact and easy to find when the motion planning problem is 'obviously impossible," avoiding complex geometric and combinatorial calculations. We demonstrate such a prover in action for a simple, yet still realistic, motion planning problem. When it fails, the prover suggests key milestones, or configurations of the robot that can then be passed on and used by a PRM planner. Thus by hitting the motion planning problem from both ends, we hope to resolve the existence of a path, except in truly delicate border-line situations.

IntroductionWe revisit the notion of kinetic efficiency for noncanonically-defined discrete attributes of moving data, like binary space partitions and triangulations.Under very general computational models, we obtain lower bounds on the minimum amount of work required to maintain any binary space partition of moving segments in the plane or any Steiner triangulation of moving points in the plane.Such lower bounds-the first to be obtained in the kinetic context-are necessary to evaluate the efliciency of kinetic data structures when the attribute to be maintained is not canonically defined.

No abstract available.

Given n line segments in the plane, the Bentley-Ottmann sweep maintains the exact ordering of the intersections of the segments with a vertical line, as this line sweeps the plane from left to right. To accomplish this, every intersection between two segments must be processed, and the running time of the sweep can be \\Omega\\Gamma n 2 ). In this paper, it is shown how a heap on the intersections can be maintained during the sweep. This new type of sweep processes O(n log 2 n) intersections when sweeping over lines and O(n p n log n) intersections when sweeping over line segments. A lower bound of \\Omega\\Gamma n log n) is also established. 1 Introduction One of the common introductory problems in geometric algorithms is that of finding all pairwise intersections in a family of line segments in the plane. The first nontrivial solution to this problem was given by Bentley and Ottmann [BO79], who introduced in 1979 the now familiar line sweep paradigm. A vertical line is moved (`swe...

this paper is to study and validate the use of the kinetic data structures proposed in [BGH97] in practice. The implementation and experimental evaluation of such structures brings to light several important issues which were not addressed in the original paper. For instance, KDSs implement the continuous maintenance of the function of interest through a discrete-event simulation. The calculation of the event times poses numerical difficulties which raise questions about the integrity of the structure if nearby events should happen out of order, or if the time of an event changes when recalculated. Also, the algorithmic measures for evaluating the quality of KDSs in [BGH97] are all worst-case measures, which may not reflect behavior under ordinary motions which occur in practice. It may well be that simple data structures do better in such situations. In order to study these issues, we have compared the KDSs of [BGH97] with simpler variants under various common data/motion distributions, each meant to generate a different amount of

A kinetic data structure for the maintenance of a multidimensional range search tree is introduced.This structure is used as a building block to obtain kinetic data structures for two classical geometric proximity problems in arbitrary dlmensions: the first structure maintains the closest pair of a set of continuously moving points, and is provably efficient.The second structure maintains a spanning tree of the moving points whose cost remains within some prescribed factor of the minimum spanning tree.

We initiate a probabilistic study of configuration functions of moving points.In our probabilistic model, a particle is given an initiaf position and a velocity drawn independently at random from the same distribution D. We show that if n particles are drawn independently at random from the uniform distribution on the square, their convex hull undergoes El(logz n) combinatorial changes in expectation, their Voronoi diagram undergoes e(n312 ) combinatorial changes, and their closest pair undergoes El(n) combinatorial changes.