| dc.identifier.uri | http://hdl.handle.net/11401/77699 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dc.type | Dissertation | |
| dcterms.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. | |
| dcterms.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. | |
| dcterms.available | 2017-09-20T16:53:21Z | |
| dcterms.contributor | Mitchell, Joseph S. B. | en_US |
| dcterms.contributor | Arkin, Esther | en_US |
| dcterms.contributor | Hu, Jiaqiao | en_US |
| dcterms.contributor | Gao, Jie. | en_US |
| dcterms.creator | Huang, Kan | |
| dcterms.dateAccepted | 2017-09-20T16:53:21Z | |
| dcterms.dateSubmitted | 2017-09-20T16:53:21Z | |
| dcterms.description | Department of Applied Mathematics and Statistics. | en_US |
| dcterms.extent | 100 pg. | en_US |
| dcterms.format | Monograph | |
| dcterms.format | Application/PDF | en_US |
| dcterms.identifier | http://hdl.handle.net/11401/77699 | |
| dcterms.issued | 2015-12-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2017-09-20T16:53:21Z (GMT). No. of bitstreams: 1
Huang_grad.sunysb_0771E_12335.pdf: 1062506 bytes, checksum: 0bb413dd4ccf48e69562cebb551caa88 (MD5)
Previous issue date: 1 | en |
| dcterms.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dcterms.subject | Applied mathematics | |
| dcterms.subject | Computational Geometry, Geometric Hitting, Online Routing, Optimization | |
| dcterms.title | Analysis of Three Geometric Optimization Problems: Local Greedy Routing in Triangulations, Touring Sequences of Polygons, and Hitting Sets of Segments | |
| dcterms.type | Dissertation | |
