Bunting, Helen Anna Louise; (1994) Results in discrete geometry. Doctoral thesis (Ph.D), UCL (University College London).

Text out.pdf Download (2MB)

Abstract

This thesis deals with three different areas within the subject of discrete geometry. Firstly I prove an upper bound and give an example that yields a lower bound, to show that the maximum number f{d, n) of rich cells in an arrangement of n hyperplanes in Rd is f(d,n) = &thetas;(nd-2). A cell of the arrangement is called rich if it is bounded non-trivially by every hyperplane. I define convex position for hyperplanes in Rd, and show that the Carathéodory number for lines in the plane is five. I consider extending these ideas, but show that a Helly number without redundancy does not exist for general convex sets, though for halfspaces d + 2 is such a number. In the second chapter I consider the 180° art gallery problem. I show that the number, f180(n), of guards required to survey a simple polygon with n sides is f180(n) ≤ [(4n + 1)/9], if their angle of vision is restricted to at most 180°. This result has since been extended and the bound currently stands at [2n/5]. I prove that on the class of monotone polygons the bounds are identical with those obtained when guards may survey a full rotation: f180(n) = min{[n/3], [r/2] + 1}, for a monotone polygon with n vertices, r of which are reflex. I also show that f0 (n) ≤ [n/2] for 0 < 180°; that f60(n) ≤ n-2; and that f0(n) ≥ n - 2 for 0 < 60°. In the final chapter I describe an algorithm that answers the 3-dimensional diameter problem in a worst-case time of O(n3/2 log n). Previously only a sketch of this algorithm existed, in a paper by Chazelle, here I describe the algorithm in detail. For a long time this was the best known algorithm, however during the preparation of this thesis I have heard of the discovery of a new algorithm for the diameter that runs in an optimal time of O(n log n).

Download activity - last month

Export as CSVJSONXML

Download activity - last 12 months

Export as CSVJSONXML

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item