Type
Text
Type
Dissertation
Advisor
Mitchell, Joseph S.B. | Mitchell, Joseph | Arkin, Esther | Gao, Jie | Bender, Michael | Yousefi, Arash.
Date
2015-08-01
Keywords
computational geometry, polygon partitioning | Computer science
Department
Department of Computer Science.
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/77291
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
We study partitioning problems of polygonal domains under requirements of balancing various objective functions. Some of them are specific to Air Traffic Management, but others are more general and have a broader range of applications. In Chapter 2 we start with a Districting problem, where we are given a partition of a polygon into weighted polygonal subdistricts, and are asked to merge them into a given number of districts while balancing their weights. We consider the problem in 1D and 2D, and the static and dynamic versions of the problem. We show that in 1D this problem is polynomially solvable, and becomes NP-complete in 2D. We give approximation algorithms for several special cases of the problem. In Chapter 3 we study the Airspace Sectorization problem, where the goal is to find a sectorization, i.e. | a partition of the airspace into sectors, under a number of requirements on the geometry of the sectors, as well as on the air traffic flow-conformance, while balancing the controllers' workload. In Chapter 4 we propose a Local Redesigning Method (LRM), a heuristic that rebalances a given disbalanced sectorization by applying small local adjustments to the sectors boundaries. We evaluate LRM experimentally on synthetically generated scenarios as well as on the real historical traffic data and demonstrate that the sectorizations produced by our method are superior in comparison with the current sectorizations of the US airspace. In Chapter 5 we propose a point-balancing convex polygonal partitioning problem defined in the following way: Given a polygon and a set of points in it, partition the polygon into the minimum number of convex pieces having a limited number of points in each piece. We present two optimal algorithms for the case of a simple polygon with some restrictions on the partitioning cuts. We also give a number of approximation algorithms for different variations of the problem. | 95 pages
Recommended Citation
Kostitsyna, Irina, "Balanced Partitioning of Polygonal Domains" (2015). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 3112.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/3112