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

Joondong Kim; Joseph S.B. Mitchell; Valentin Polishchuk; Arto Vihavainen

doi:10.1145/1377676.1377717

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

Joondong Kim
, Joseph S.B. Mitchell
, Valentin Polishchuk
, Arto Vihavainen

Applied Mathematics and Statistics

Stony Brook University
University of Helsinki

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

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 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.

Original language	English
Title of host publication	Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Pages	230-231
Number of pages	2
DOIs	https://doi.org/10.1145/1377676.1377717
State	Published - 2008
Event	24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States Duration: Jun 9 2008 → Jun 11 2008

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Conference

Conference	24th Annual Symposium on Computational Geometry, SCG'08
Country/Territory	United States
City	College Park, MD
Period	06/9/08 → 06/11/08

Keywords

Algorithms

Access to Document

10.1145/1377676.1377717

Cite this

@inproceedings{a88bc623d9b049c681ddf3322ff4dca0,

title = "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 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.",

keywords = "Algorithms",

author = "Joondong Kim and Mitchell, \{Joseph S.B.\} and Valentin Polishchuk and Arto Vihavainen",

year = "2008",

doi = "10.1145/1377676.1377717",

language = "English",

isbn = "9781605580715",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "230--231",

booktitle = "Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08",

note = "24th Annual Symposium on Computational Geometry, SCG'08 ; Conference date: 09-06-2008 Through 11-06-2008",

}

Kim, J, Mitchell, JSB, Polishchuk, V & Vihavainen, A 2008, Routing a maximum number of disks through a scene of moving obstacles. in Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08. Proceedings of the Annual Symposium on Computational Geometry, pp. 230-231, 24th Annual Symposium on Computational Geometry, SCG'08, College Park, MD, United States, 06/9/08. https://doi.org/10.1145/1377676.1377717

Routing a maximum number of disks through a scene of moving obstacles. / Kim, Joondong; Mitchell, Joseph S.B.; Polishchuk, Valentin et al.
Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08. 2008. p. 230-231 (Proceedings of the Annual Symposium on Computational Geometry).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Kim, Joondong

AU - Mitchell, Joseph S.B.

AU - Polishchuk, Valentin

AU - Vihavainen, Arto

PY - 2008

Y1 - 2008

N2 - 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 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.

AB - 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 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.

KW - Algorithms

UR - https://www.scopus.com/pages/publications/57349192029

U2 - 10.1145/1377676.1377717

DO - 10.1145/1377676.1377717

M3 - Conference contribution

AN - SCOPUS:57349192029

SN - 9781605580715

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 230

EP - 231

BT - Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08

T2 - 24th Annual Symposium on Computational Geometry, SCG'08

Y2 - 9 June 2008 through 11 June 2008

ER -

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this