TREKKING IN THE ALPS WITHOUT FREEZING OR GETTING TIRED

Let F be a polyhedral terrain with n vertices, We show how to preproce ss F such that for any two query points on F it can be decided whether there exists a path on F between the two points whose height decrease s monotonically. More generally, the minimum total ascent or descent a long any path between the two points can be computed. It is also possi ble to decide, given two query points and a height, whether there is a path that stays below this height. All these queries can be answered with one data structure which stores the so-called height-level map of the terrain. Although the height-level mao has quadratic worst-case c omplexity, it is stored implicitly using only linear storage. The quer y rime for all the above queries is O(log n) and the structure can be built in O(n log n) time. A path with the desired property can be repo rted in additional time that is linear in the description size of the path.