• Information Technology
  • Human Resources
  • Careers
  • Giving
  • Library
  • Bookstore
  • Active Living
  • Continuing Education
  • Go Dinos
  • UCalgary Maps
  • UCalgary Directory
  • Academic Calendar
My UCalgary
Webmail
D2L
ARCHIBUS
IRISS
  • Faculty of Arts
  • Cumming School of Medicine
  • Faculty of Environmental Design
  • Faculty of Graduate Studies
  • Haskayne School of Business
  • Faculty of Kinesiology
  • Faculty of Law
  • Faculty of Nursing
  • Faculty of Nursing (Qatar)
  • Schulich School of Engineering
  • Faculty of Science
  • Faculty of Social Work
  • Faculty of Veterinary Medicine
  • Werklund School of Education
  • Information TechnologiesIT
  • Human ResourcesHR
  • Careers
  • Giving
  • Library
  • Bookstore
  • Active Living
  • Continuing Education
  • Go Dinos
  • UCalgary Maps
  • UCalgary Directory
  • Academic Calendar
  • Libraries and Cultural Resources
View Item 
  •   PRISM Home
  • Graduate Studies
  • The Vault: Electronic Theses and Dissertations
  • View Item
  •   PRISM Home
  • Graduate Studies
  • The Vault: Electronic Theses and Dissertations
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Some Problems on Graphs and Arrangements of Convex Bodies

Thumbnail
View
Thesis
Download
Thesis (2.244Mb)
Advisor
Bezdek, Karoly
Author
Khan, Muhammad Ali
Committee Member
Pivovarov, Peter
Ling, Joseph
Woodrow, Robert
Seyffarth, Karen
Other
Discrete Geometry
Graph Theory
Convex Geometry
Computational Geometry
Algorithms
Subject
Mathematics
Computer Science
Type
Thesis
Metadata
Show full item record

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.
Corporate
University of Calgary
Faculty
Graduate Studies
Doi
http://dx.doi.org/10.5072/PRISM/27829
Uri
http://hdl.handle.net/11023/3765
Collections
  • The Vault: Electronic Theses and Dissertations

Browse

All of PRISMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors

  • Email
  • SMS
  • 403.220.8895
  • Live Chat

Energize: The Campaign for Eyes High

Privacy Policy
Website feedback

University of Calgary
2500 University Drive NW
Calgary, AB T2N 1N4
CANADA

Copyright © 2017