UCT CS Research Document Archive

Proof of Field D*'s Case Separation for Arbitrary Simplices

Merry, Bruce, Simon James Perkins, Patrick Marais and James Gain (2012) Proof of Field D*'s Case Separation for Arbitrary Simplices. Technical Report CS12-07-00, Department of Computer Science, University of Cape Town.

Full text available as:
PDF - Requires Adobe Acrobat Reader or other PDF viewer.


In their development of the Field D* algorithm, Ferguson et. al. prove that a path through a unit length right-angled triangle originating from an interpolated edge, and travelling to the opposite vertex must either be a direct or indirect case. A combination of the two is not optimal. Later work, proves this for arbitrary, but non-degenerate triangles.

In this technical report, we prove the same for non-degenerate simplices, which are generalisations of triangles to higher dimensions.

EPrint Type:Departmental Technical Report
Keywords:computational geometry
mathematical proof
Subjects:I Computing Methodologies: I.2 ARTIFICIAL INTELLIGENCE
ID Code:785
Deposited By:Perkins, Simon
Deposited On:25 September 2012