β-skeletons are defined by Kirkpatrick and Radke in [10]. They are used to describe proximity relationships between points. A Minimum Weight Triangulation (MWT) of a set of points is a triangulation that has the minimum total edge length among all triangulations. Researchers have been attempting for years to find efficient algorithms for finding MWTs. However, it is still unknown as to whether constructing a MWT can be performed in polynomial time [11, page 288], is NP-hard or is something else entirely....[ Read more ]

β-skeletons are defined by Kirkpatrick and Radke in [10]. They are used to describe proximity relationships between points. A Minimum Weight Triangulation (MWT) of a set of points is a triangulation that has the minimum total edge length among all triangulations. Researchers have been attempting for years to find efficient algorithms for finding MWTs. However, it is still unknown as to whether constructing a MWT can be performed in polynomial time [11, page 288], is NP-hard or is something else entirely.

Minimum weight triangulations are objects still not very well understood. In fact, until recently no one knew of any sub-graph that was guaranteed to be part of the MWT. Then Keil [9] proved that the [square root 2]-skeleton is a sub-graph of every MWT. Improving upon his results, Cheng and Xu [2] pushed his technique to the limit and proved that the 1.17862...-skeleton is a sub-graph of every MWT.

Their results have given us a chance of designing efficient algorithms to compute MWTs. Given a set of points, we now know a set of edges that must be in the MWT. This helps to cut the computation effort of constructing the MWT significantly if not drastically. In this thesis, we utilize their results to design and implement an algorithm to compute the MWT for larger point sets than were previously possible. In addition to this, we also analyze some properties of β-skeletons of random points.