Files and links (1)
PDFOpen Access (License Unspecified), Open Access
Dissertation
Problems in extremal and combinatorial geometry
Doctor of Philosophy (Ph.D.), Drexel University
Jun 2012
DOI:
https://doi.org/10.17918/00001208
Abstract
This thesis deals with three families of optimization problems: (1) Euclidean optimization problems on random point sets; (2) independent sets in hypergraphs; and (3) packings in point lattices. First, we consider bounds on several monochromatic and bichromatic optimization problems including minimum matching, minimum spanning trees, and the travelling salesman problem. Many of these problems lend themselves to representations in terms of hierarchically separated trees - trees with uniform branching factor and depth, and having edge weights exponential in the depth of the edge in the tree. In the second part, we consider the independent set problem on uniform hypergraphs, in anticipation of applying it to the third part, packing problems on point lattices. In these problems we wish to select a subset of points from an n n ::: n grid avoiding particular patterns. We also study several generalizations of these problems that have not been handled previously.
Metrics
33 File views/ downloads
82 Record Views
Details
- Title
- Problems in extremal and combinatorial geometry
- Creators
- Thomas A. Plick
- Contributors
- Ali Shokoufandeh (Advisor) - Drexel University, Computer Science (Computing)
- Awarding Institution
- Drexel University
- Degree Awarded
- Doctor of Philosophy (Ph.D.)
- Publisher
- Drexel University; Philadelphia, Pennsylvania
- Resource Type
- Dissertation
- Language
- English
- Academic Unit
- College of Arts and Sciences; Drexel University; Mathematics
- Other Identifier
- 991018931815504721