Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  16 Sep 2013 
Place of Publication  Utrecht 
Publisher  
Publication status  Published  2013 
Fingerprint
Cite this
}
Realistic analysis for algorithmic problems on geographical data. / Driemel, A.
Utrecht : Utrecht University, 2013. 217 p.Research output: Thesis › Phd Thesis 4 Research NOT TU/e / Graduation NOT TU/e)
TY  THES
T1  Realistic analysis for algorithmic problems on geographical data
AU  Driemel, A.
PY  2013
Y1  2013
N2  The worstcase analysis is a key element of the performance analysis of algorithms. When it comes to spatial data, such as paths of moving objects and digital terrain models, the theoretical worst case may be a contrived configuration which would never occur in practice. In this case the algorithmic analysis may fail to describe the actual behavior of an algorithm. To remedy this, a collection of techniques have been developed, which enable a realistic analysis with mathematically provable bounds. Realistic input models capture geometric parameters such as the distribution and shape of the input objects. This allows for a specific analysis that takes the difficulty of the input instance into account and is therefore also meaningful for input instances that are less difficult. In this thesis we revisit some wellstudied problems of computational geometry with a realistic analysis. We first study the Frechet distance, a similarity measure for outlines of shapes or paths of moving objects. Under a new realistic input model, we can approximate the Frechet distance in nearlinear time, where previous algorithms run in quadratic time. We extend our algorithm so that it can be applied to a sophisticated variant, the shortcut Frechet distance, which captures partial similarity. We show that computing this new variant exactly is NPhard. Along the way, we develop data structures to answer Frechetdistance queries. In the second part of the thesis, we study computations on digital terrain models, which represent geographic regions. A terrain model can be used to simulate where rain water flows to, which is useful for flood prediction for instance. Although these computations are extremely sensitive to elevation error, none of the known algorithms take noise into account. We develop a theory that enables robust and efficient hydrological computations if the elevation data from which the terrain model was derived was imprecise. While the new theory uses fixed flow directions, we also show that an extension of our methods to continuous directions will be difficult. In particular, we show that it is NPhard to determine if there can be a steepest descent path between two points on an imprecise polyhedral surface. The Voronoi diagram is an important geometric structure that can be used to answer queries for the closest point of interest. The "closeness" can be defined by the length of the shortest path along the terrain surface. The efficiency depends among other things on the amount of space taken up by the diagram. According to the classical worstcase analysis the space grows quadratically with the size of the terrain. However, this quadratic behavior cannot be observed in practice. In the last part of the thesis we analyze the size of the Voronoi diagram under the assumption that the points of interest are distributed uniformly on the terrain surface. Our results confirm a conjecture by Aronov, de Berg and Thite from 2008 that in a realistic setting the complexity of the diagram is additively linear in the size of the terrain and the number of sites.
AB  The worstcase analysis is a key element of the performance analysis of algorithms. When it comes to spatial data, such as paths of moving objects and digital terrain models, the theoretical worst case may be a contrived configuration which would never occur in practice. In this case the algorithmic analysis may fail to describe the actual behavior of an algorithm. To remedy this, a collection of techniques have been developed, which enable a realistic analysis with mathematically provable bounds. Realistic input models capture geometric parameters such as the distribution and shape of the input objects. This allows for a specific analysis that takes the difficulty of the input instance into account and is therefore also meaningful for input instances that are less difficult. In this thesis we revisit some wellstudied problems of computational geometry with a realistic analysis. We first study the Frechet distance, a similarity measure for outlines of shapes or paths of moving objects. Under a new realistic input model, we can approximate the Frechet distance in nearlinear time, where previous algorithms run in quadratic time. We extend our algorithm so that it can be applied to a sophisticated variant, the shortcut Frechet distance, which captures partial similarity. We show that computing this new variant exactly is NPhard. Along the way, we develop data structures to answer Frechetdistance queries. In the second part of the thesis, we study computations on digital terrain models, which represent geographic regions. A terrain model can be used to simulate where rain water flows to, which is useful for flood prediction for instance. Although these computations are extremely sensitive to elevation error, none of the known algorithms take noise into account. We develop a theory that enables robust and efficient hydrological computations if the elevation data from which the terrain model was derived was imprecise. While the new theory uses fixed flow directions, we also show that an extension of our methods to continuous directions will be difficult. In particular, we show that it is NPhard to determine if there can be a steepest descent path between two points on an imprecise polyhedral surface. The Voronoi diagram is an important geometric structure that can be used to answer queries for the closest point of interest. The "closeness" can be defined by the length of the shortest path along the terrain surface. The efficiency depends among other things on the amount of space taken up by the diagram. According to the classical worstcase analysis the space grows quadratically with the size of the terrain. However, this quadratic behavior cannot be observed in practice. In the last part of the thesis we analyze the size of the Voronoi diagram under the assumption that the points of interest are distributed uniformly on the terrain surface. Our results confirm a conjecture by Aronov, de Berg and Thite from 2008 that in a realistic setting the complexity of the diagram is additively linear in the size of the terrain and the number of sites.
UR  http://igiturarchive.library.uu.nl/dissertations/20130830200458/driemel.pdf
M3  Phd Thesis 4 Research NOT TU/e / Graduation NOT TU/e)
PB  Utrecht University
CY  Utrecht
ER 