KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS

DOI10.1142/S0218195902000724zbMath1152.68671MaRDI QIDQ4818544

Bettina Speckmann, Jack Scott Snoeyink, David G. Kirkpatrick

Publication date: 29 September 2004

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

collision detectionkinetic data structuresminimum link separation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Kinetic collision detection with fast flight plan changes ⋮ A package for exact kinetic data structures and sweepline algorithms ⋮ Minimum weight pseudo-triangulations ⋮ Kinetic and dynamic data structures for convex hulls and upper envelopes ⋮ Convexity minimizes pseudo-triangulations ⋮ A kinetic triangulation scheme for moving points in the plane ⋮ The stochastic walk algorithms for point location in pseudo-triangulations ⋮ Kinetic collision detection between two simple polygons. ⋮ Decomposing a simple polygon into pseudo-triangles and convex polygons ⋮ Flips in edge-labelled pseudo-triangulations ⋮ On the number of pseudo-triangulations of certain point sets ⋮ Kinetic facility location ⋮ Kinetic collision detection for balls ⋮ Kinetic collision detection for convex fat objects

Cites Work

• Ray shooting in polygons using geodesic triangulations
• Coordinated motion planning for two independent robots
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
• A compact piecewise-linear Voronoi diagram for convex sites in the plane
• A “retraction” method for planning the motion of a disc
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• Efficiently Planning Compliant Motion in the Plane