School of Mathematics and Statistics - Theses

Permanent URI for this collection

http://hdl.handle.net/11343/295

Filters

2014 - 2019 2
1 1
Reset filters

Settings
Statistics
Citations
Start date: 1972 × Type: PhD thesis × Subject: discrete geometry ×

Search Results

Now showing 1 - 2 of 2
  • Item
    Thumbnail Image
    Degree bounded geometric spanning trees with a bottleneck objective function
    Andersen, Patrick ( 2019)
    We introduce the geometric $\delta$-minimum bottleneck spanning tree problem ($\delta$-MBST), which is the problem of finding a spanning tree for a set of points in a geometric space (e.g., the Euclidean plane) such that no vertex in the tree has a degree that exceeds $\delta$, and the length of the longest edge in the tree is minimum. We give complexity results for this problem and describe several approximation algorithms whose performances we investigate, both analytically and through computational experimentation.
  • Item
    Thumbnail Image
    Combinatorial geometry of point sets with collinearities
    PAYNE, MICHAEL ( 2014)
    In this thesis various combinatorial problems relating to the geometry of point sets in the Euclidean plane are studied. The unifying theme is that all the problems involve point sets that are not in general position, but have some collinearities. Topics addressed include; Dirac's conjecture related to the maximum degree of visibility graphs, Erdős' general position subset selection problem, connectivity properties of visibility graphs, visibility in bichromatic point sets, and empty pentagons in point sets with collinearities.