Some Problems on Graphs and Arrangements of Convex Bodies
| atmire.migration.oldid | 5532 | |
| dc.contributor.advisor | Bezdek, Károly | |
| dc.contributor.author | Khan, Muhammad Ali | |
| dc.contributor.committeemember | Pivovarov, Peter | |
| dc.contributor.committeemember | Ling, Joseph | |
| dc.contributor.committeemember | Woodrow, Robert | |
| dc.contributor.committeemember | Seyffarth, Karen | |
| dc.date.accessioned | 2017-05-01T15:58:07Z | |
| dc.date.available | 2017-05-01T15:58:07Z | |
| dc.date.issued | 2017 | |
| dc.date.submitted | 2017 | en |
| dc.description.abstract | Arrangements of convex bodies are ubiquitous in discrete geometry. Covering and packing problems are two major classes of problems arising from these arrangements. This thesis makes contributions to some open questions on covering a convex body by its homothetic copies and packings of translates of a convex body. The packings we study lead to the notion of a contact graph, a tool used by mathematicians, material scientists and physicists while investigating these packings. This brings a combinatorial flavour to this thesis and leads to the algorithmic question of generating graphs and hypergraphs with desired properties. We introduce the covering index of a convex body as a measure of how economically the body can be covered by a relatively few smaller positive homothetic copies. Determining the covering index can be thought of as a quantitative version of the sixty-year old Covering Conjecture in discrete and convex geometry. We prove several interesting properties of the covering index, compute its values for large classes of convex bodies and use it to devise an approach to attack the Covering Conjecture. We then consider the problem of determining the separable Hadwiger number of a smooth convex domain and the maximum contact numbers of totally separable translative packings of a smooth strictly convex domain. Both these questions have links with crystallography and self-assembly of material particles, and are completely solved here. Moreover, we show that for smooth Radon domains the extremal packings always lie on special kinds of lattices and characterize the underlying contact graphs. Next, we fully address the algorithmic questions of constructing tournaments from their imbalance sets and hypertournaments from their score sequences. The former relates to the Equal-Sum Subsets problem from computer science, while the latter is a special instance of the degree sequence problem that asks for the generation of all graphs or hypergraphs in some large class that have the same degree sequence. We characterize imbalance sets of tournaments, give an algorithm to generate tournaments from their imbalance sets and define a rapidly mixing Markov chain that uniformly samples all hypertournaments with a given score sequence. | en_US |
| dc.identifier.citation | Khan, M. A. (2017). Some Problems on Graphs and Arrangements of Convex Bodies (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/27829 | en_US |
| dc.identifier.doi | http://dx.doi.org/10.11575/PRISM/27829 | |
| dc.identifier.uri | http://hdl.handle.net/11023/3765 | |
| dc.language.iso | eng | |
| dc.publisher.faculty | Graduate Studies | |
| dc.publisher.institution | University of Calgary | en |
| dc.publisher.place | Calgary | en |
| dc.rights | University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission. | |
| dc.subject | Mathematics | |
| dc.subject | Computer Science | |
| dc.subject.other | Discrete Geometry | |
| dc.subject.other | Graph Theory | |
| dc.subject.other | Convex Geometry | |
| dc.subject.other | Computational Geometry | |
| dc.subject.other | Algorithms | |
| dc.title | Some Problems on Graphs and Arrangements of Convex Bodies | |
| dc.type | doctoral thesis | |
| thesis.degree.discipline | Mathematics and Statistics | |
| thesis.degree.grantor | University of Calgary | |
| thesis.degree.name | Doctor of Philosophy (PhD) | |
| ucalgary.item.requestcopy | true |