Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection

DOI10.1137/0219020zbMath0696.68044OpenAlexW2034181461MaRDI QIDQ3474274

Pankaj K. Agarwal, Micha Sharir

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219020

zbMATH Keywords

arrangementsmotion planningcomputational geometryrandom samplingDavenport-Schinzel-sequences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other problems of combinatorial convexity (52A37) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Related Items (11)

Bottleneck bichromatic full Steiner trees ⋮ Computing depth orders and related problems ⋮ Computing depth orders for fat objects and related problems ⋮ On fat partitioning, fat covering and the union size of polygons ⋮ Range queries on uncertain data ⋮ Preprocessing chains for fast dihedral rotations is hard or even impossible. ⋮ Partitioning arrangements of lines. I: An efficient deterministic algorithm ⋮ Partitioning arrangements of lines. II: Applications ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ Counting and representing intersections among triangles in three dimensions ⋮ Reporting intersecting pairs of convex polytopes in two and three dimensions

This page was built for publication: Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection