Type
Text
Type
Thesis
Advisor
Joseph S.B. Mitchell. | Jie Jie Gao. .
Date
2011-05-01
Keywords
Computational Geometry, Geometric Partition, Load Balancing, Optimization Problem | 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/71701
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
Motivated by the airspace sectorization problem in air traffic management, we consider the following family of geometric partitioning problems: Given a finite set of points within a geometric domain, we want to partition the domain, and thereby the point set, in order that the resulting disjoint polygonal pieces are load-balanced, so that each piece contains a specified number of points and satisfies specified geometric constraints, such as fatness (aspect ratio), convexity of the pieces, etc. We consider different variations of the problem having various optimization criteria, including measures of the balance in terms of areas of pieces, number of points per piece, and total length of the edges defining the partition.
Recommended Citation
Srihari, Yogesh Mysore, "On Balanced Geometric Point Set Partitioning Problems" (2011). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 906.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/906