COMPUTATIONAL GEOMETRY I, II


This has appeared as Chapters 19 and 20 in 


Author:
D. T. Lee
Institute of Information Science
Academia Sinica
Nankang, Taipei, Taiwan 115

also with 
Department of Electrical and Computer Engineering, Northwestern University
Evanston, IL 60208
Department of Electrical Engineering and Computer Science, 
University of Illinois at Chicago, Chicago, IL 60607 

e-mail: dtlee@ieee.org 

Introduction

Computational geometry, since its inception in 1975, has received a great deal of 
attention from researchers in the area of design and analysis of algorithms.  
It has evolved into a discipline of its own.  It is concerned with the computational 
complexity of geometric problems that arise in various disciplines such as pattern 
recognition, computer graphics, geographical information system, computer vision, 
CAD/CAM, robotics, VLSI layout, operations research, statistics, etc.  

In contrast with the classical approach to proving mathematical theorems about 
geometry-related problems, this discipline emphasizes the computational aspect of 
these problems and attempts to exploit the underlying geometric properties possible, 
e.g., the metric space, to derive efficient algorithmic solutions.  

An objective of this discipline in the theoretical context is to study the computational 
complexity (giving lower bounds) of geometric problems, and to devise efficient 
algorithms (giving upper bounds) whose complexity preferably matches the lower bounds.  
That is, not only are we interested in the intrinsic difficulty of geometric 
computational problems under a certain computation model, but we are also concerned 
with the algorithmic solutions that are efficient or provably optimal in the worst 
or average case.  In this regard, the asymptotic time (or space)  complexity
of an algorithm, i.e., the behavior of an algorithm, as the input size approaches 
infinity, is of interest. Due to its applications to various science and engineering 
related disciplines, researchers in this field have begun to address the efficacy 
of the algorithms, the issues concerning robustness and numerical stability, 
and the actual running times of their implementions.

In this and the following chapter we concentrate mostly on the theoretical development 
of this field in the context of sequential computation, and discuss a number
of typical topics and the algorithmic approaches as well as some discussions of 
geometric software that is under development.  We will adopt the real 
RAM (Random Access Machine) model of computation in which all arithmetic operations, 
comparisons, k-th-root, exponential or logarithmic functions take unit time.