ABSTRACT

Computational geometry is defined broadly as the design and analysis of algorithms for solving problems involving geometric objects. Use of the term ‘computational geometry’ and its meaning differs in different application contexts. Most researchers in computer science interpret the subject as design and optimization of algorithms involving geometric problems. The term ‘algorithm design’ carries the connotation of discrete algorithms as opposed to the algorithms used in numerical analysis. The numerical analysis problems are used for solving computational problems in continuous domains. Computational geometry is useful in solving problems of discrete combinatorial geometry rather than continuous geometry. This chapter describes the computational geometric algorithms in the context of their applications in GIS and how these algorithms are used to process spatial data which are the primary inputs of GIS.