Routing a maximum number of disks through a scene of moving obstacles

ABSTRACT

This video illustrates an algorithm for computing a maximum number of disjoint paths for unit disks moving among a set of dynamic obstacles in the plane. The problem is motivated by applications in air traffic management: aircraft must be routed while avoiding no-fly zones and weather constraints and while maintaining at least a specified horizontal separation distance between themselves. Given a polygonal domain with moving obstacles, our goal is to determine the maximum number of unit disks (aircraft with safety zones) that can be routed safely through the domain, entering/exiting through specified edges of the domain.

The video is meant to accompany the paper [1], which gives details of the algorithm and its analysis.

REFERENCES

• 1: Esther M. Arkin , Joseph S.B. Mitchell , Valentin Polishchuk, Maximum thick paths in static and dynamic environments, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA [doi>10.1145/1377676.1377682]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms

Keywords:
approximation algorithms, maximum throughput, motion planning, moving obstacles