Morgan, David Andrew;
(1992)
Aspects Of Combinatorial Geometry.
Doctoral thesis (Ph.D), UCL (University College London).
![]() |
Text
Aspects_of_combinatorial_geome.pdf Download (2MB) |
Abstract
This thesis presents solutions to various problems in the expanding field of combinatorial geometry. Chapter 1 gives an introduction to the theory of the solution of an integer programming problem, that is maximising a linear form with integer variables subject to a number of constraints. Since the maximum value of the linear form occurs at a vertex of the convex hull of integer points defined by the constraints, it is of interest to estimate the number of these vertices. Chapter 2 describes the application of certain geometrical interpretations of number theory to the solution of integer programming problems in the plane. By using, in part, the well-known Klein interpretation of continued fractions, a method of constructing the vertices of the convex hull of integer points defined by particular constraints is developed. Bounds for the number of these vertices and properties of certain special cases are given. Chapter 3 considers the general d-dimensional integer programming problem. Upper and lower bounds are presented for the number of vertices of the convex hull of integer points defined by particular constraints. Chapter 4 is concerned with the approximation of convex sets by convex polytopes. First, a detailed description of recent work on minimal circumscribing triangles for convex polygons and the extension to minimal circumscribing equilateral triangles is given. This leads to a new approach to constructing a Borsuk Division and finding a regular hexagon circumscribing a convex polygon. Then, a method of approximating general convex sets by convex polytopes is presented, leading to consideration of the problem of a d-simplex approximating a d-ball. Chapter 5 develops algorithms for finding points with particular combinatorial properties, using containment objects such as balls, closed half-spaces and ellipsoids. Chapter 6 gives a new approach to the problem of inscribing a square in a convex polygon, leading to possible ideas for an algorithm.
Type: | Thesis (Doctoral) |
---|---|
Qualification: | Ph.D |
Title: | Aspects Of Combinatorial Geometry |
Open access status: | An open access version is available from UCL Discovery |
Language: | English |
Additional information: | Thesis digitised by ProQuest. |
URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10121662 |
Archive Staff Only
![]() |
View Item |