Springer Verlag, Lecture Notes in Computer Science, p. 35-45
DOI: 10.1007/978-3-662-48971-0_4
World Scientific Publishing, International Journal of Computational Geometry and Applications, 01n02(27), p. 13-32, 2017
DOI: 10.1142/s0218195917600020
Full text: Download
We propose an algorithm for finding a [Formula: see text]-approximate shortest path through a weighted 3D simplicial complex [Formula: see text]. The weights are integers from the range [Formula: see text] and the vertices have integral coordinates. Let [Formula: see text] be the largest vertex coordinate magnitude, and let [Formula: see text] be the number of tetrahedra in [Formula: see text]. Let [Formula: see text] be some arbitrary constant. Let [Formula: see text] be the size of the largest connected component of tetrahedra whose aspect ratios exceed [Formula: see text]. There exists a constant [Formula: see text] dependent on [Formula: see text] but independent of [Formula: see text] such that if [Formula: see text], the running time of our algorithm is polynomial in [Formula: see text], [Formula: see text] and [Formula: see text]. If [Formula: see text], the running time reduces to [Formula: see text].