[Packing and Covering with Centrally Symmetric Convex Discs]

by

Acknowledgement

I would take this opportunity to thank my research supervisor, family and friends for their support and guidance without which this research would not have been possible.

DECLARATION

I, [type your full first names and surname here], declare that the contents of this dissertation/thesis represent my own unaided work, and that the dissertation/thesis has not previously been submitted for academic examination towards any qualification. Furthermore, it represents my own opinions and not necessarily those of the University.

Signed __________________ Date _________________

Abstract

In 1950, C.A. Rogers introduced and studied the simultaneous packing and covering constants for a convex body and obtained the first general upper bound. Afterwards, they have attracted the interests of many authors such as L. Fejes Toth, S.S. Ryskov, G.L. Butler, K. Boroczky, H. Horvath, J. Linhart and M. Henk since, besides their own geometric significance, they are closely related to the packing densities and the covering densities of the convex body, especially to the Minkowski-Hlawka theorem. However, so far our knowledge about them is still very limited. In this thesis we will determine the optimal upper bound of the simultaneous packing and covering constants for two-dimensional centrally symmetric convex domains, and characterize the domains attaining the upper bound. This thesis deals with arrangements of replicas of a plane convex body K. We prove certain sharp inequalities linking the packing and the covering densities, d(K) and ?(K), associated to this body. In particular we find the exact analytic description of the set of pairs (d(K), ? (K)) when K belongs to the class of centrally symmetric octagons.

Table of Contents

CHAPTER 1: INTRODUCTION6

The Brunn-Minkowski Theoretical Framework6

Deviation in Geometry9

High-Dimensional Geometry12

Centrally symmetric convex body18

Definition, notation and preliminaries19

Lemma 1.121

Lemma 1.221

Theorem 1 .121

Lemma 1.321

Proof22

Proof23

Theorem 1.225

Proof26

Corollary 1.129

Proof29

Corollary 1.229

Proof29

CHAPTER 2 : THE PROBLEM AND SUMMARY OF RESULTS33

Theorem 2.133

Proof of theorem 2.237

Proof of Theorem 2.343

Proof of Theorem 2.450

Proofs of Theorems 2.5 and 2.654

Conclusions and Open Problems54

CHAPTER 3: BRUNN-MINKOWSKI INEQUALITY PROOF56

Theorem 3.1 (Brunn)57

Theorem 3.2 (Brunn-Minkowski inequality)59

Theorem 3.3 (Isoperimetric inequality)59

Proof59

CHAPTER 4: THE QUEST FOR THE UPPER BOUND63

Theorem 4. 1(Kuperberg)65

Theorem 4.2 (Kuperberg)65

Theorem 4.366

The main construction66

Preliminary lemmas67

Proof67

Lemma 4.568

Proof68

Lemma 4.669

Proof70

Lemma 4.771

Proof71

Proof of theorem 4.372

Lemma 4.873

Proof73

CHAPTER 5: THE UPPER BOUND FOR A(K): CUTTING CORNERS78

Theorem 5.179

Theorem 5.279

An application: Spanning trees across barriers79

Theorem5. 380

Theorem 5.480

Related previous work on cuttings81

Preliminaries for Constructing Optimal Cuttings for Disks83

Subdivisions for Mutually Avoiding Disks84

Lemma 184

Proof of Lemma 184

CHAPTER 6: THE PROOF OF THE UPPER BOUND87

Lower Bounds87

Upper Bounds93

CHAPTER 7: CONCLUSION AND PLANS FOR THE FUTURE96

REFERENCES99

Chapter 1: Introduction

In next chapters, we consider arrangements of convex bodies in the Euclidean plane. A convex body is a compact convex set with nonempty interior; its area will be denoted by A( K). An arrangement of congruent replicas (translates) of a convex body K is a family A of convex bodies, each of which is congruent to (is translate of) K. The arrangement is a packing if its members' interiors are mutually disjoint, and it is a covering if the union of its members is the whole plane. For any pair of independent vectors u and v in E, the lattice generated by u and v is the set of vectors ...