Publications [#237002] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Sun, Z; Reif, JH, Adaptive and compact discretization for weighted region optimal path finding, in 14th Symposium on Fundamentals of Computation Theory, Malmö Högskola, Sweden, August 12-15, 2003, Springer-Verlag Lecture Notes in Computer Science, Vol. 2751, pp. 258-270, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 2751 (January, 2003), pp. 258-270, ISSN 0302-9743 [pdf], [doi]
   (last updated on 2026/02/08)

   Abstract:
   This paper presents several results on the weighted region optimal path problem. An often-used approach to approximately solve this problem is to apply a discrete search algorithm to a graph Gε generated by a discretization of the problem; this graph guarantees to contain an ε-approximation of an optimal path between given source and destination points. We first provide a discretization scheme such that the size of Gε does not depend on the ratio between the maximum and minimum unit weights. This leads to the first ε-approximation algorithm whose complexity is not dependent on the unit weight ratio. We also introduce an empirical method, called adaptive discretization method, that improves the performance of the approximation algorithms by placing discretization points densely only in areas that may contain optimal paths. BUSHWHACK is a discrete search algorithm used for finding optimal paths in Gε. We added two heuristics to BUSHWHACK to improve its performance and scalability. © Springer-Verlag Berlin Heidelberg 2003.