Type
Text
Type
Dissertation
Advisor
Mitchell, Joseph S. B. | Arkin, Esther | Hu, Jiaqiao | Gao, Jie.
Date
2015-12-01
Keywords
Applied mathematics | Computational Geometry, Geometric Hitting, Online Routing, Optimization
Department
Department of Applied Mathematics and Statistics.
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/77699
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
Finding short paths to visit places and finding small sets to hit objects are two core problems in Computational Geometry. We consider these problems in various geometric settings. The first one is greedy routing in a triangulation, which has applications in sensor networks and robotic swarm exploration. The second problem we consider is finding the shortest path to tour a sequence of polygons (TPP). We prove the problem is NP-hard if the polygons are non-convex even they are disjoint. We also obtain results on TPP with time constraints, which means the visitor is required to stay in a polygon for some time. Geometric Hitting Problem is a special case of Set Cover Problem, which is proved to have an approximation lower bound of log(n) if P ≠ NP. We consider the problem of hitting lines having limited number of orientations. For different cases, we give optimal polynomial time algorithms, approximation algorithms or NP-hardness and APX-hardness proves. | Finding short paths to visit places and finding small sets to hit objects are two core problems in Computational Geometry. We consider these problems in various geometric settings. The first one is greedy routing in a triangulation, which has applications in sensor networks and robotic swarm exploration. The second problem we consider is finding the shortest path to tour a sequence of polygons (TPP). We prove the problem is NP-hard if the polygons are non-convex even they are disjoint. We also obtain results on TPP with time constraints, which means the visitor is required to stay in a polygon for some time. Geometric Hitting Problem is a special case of Set Cover Problem, which is proved to have an approximation lower bound of log(n) if P ≠NP. We consider the problem of hitting lines having limited number of orientations. For different cases, we give optimal polynomial time algorithms, approximation algorithms or NP-hardness and APX-hardness proves. | 100 pages
Recommended Citation
Huang, Kan, "Analysis of Three Geometric Optimization Problems: Local Greedy Routing in Triangulations, Touring Sequences of Polygons, and Hitting Sets of Segments" (2015). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 3490.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/3490