This handbook provides an up-to-date compendium of fundamental computer science
topics, techniques, and applications. Along with updating and revising many of the existing …

Handbook of DISCRETE AND COMPUTATIONAL GEOMETRY Page 1 i “K25063” — 2017/9/15
— 18:58 — page 811 — i i i 31 SHORTEST PATHS AND NETWORKS Joseph SB Mitchell …

This chapter surveys computational topology results in the special, low-dimensional case
where the ambient space is a surface. Surface topology is very well-understood and …

The Fréchet distance between two curves in the plane is the minimum length of a leash that
allows a dog and its owner to walk along their respective curves, from one end to the other …

We investigate the concept of a median among a set of trajectories. We establish criteria that
a “median trajectory” should meet, and present two different methods to construct a median …

This paper addresses the path planning problem for robotic applications using homotopy
classes. These classes provide a topological description of how paths avoid obstacles …

Consider a graph drawn on a surface (for example, the plane minus a finite set of obstacle
points), possibly with crossings. We provide an algorithm to decide whether such a drawing …

We describe algorithms to compute the shortest path homotopic to a given path, or the
shortest cycle freely homotopic to a given cycle, on an orientable combinatorial surface …

We address the problem of computing homotopic shortest paths in the presence of obstacles
in the plane. Problems on homotopy of paths received attention very recently [Cabello et al …

We consider a local planner that utilizes model predictive control to locally deviate from a
prescribed global path in response to dynamic environments, taking into account the system …