\input CS445Hdr
% this is CS445N1.tex of January 18, 1982  11:51 PM

\def\title{Lecture 1}
\def\header{Introduction}

\def\th{$\null^{\hbox{th}}$ }
\def\tb{\penalty2000\hangindent10pt after 0}

\chap{1. \header.}

\sect{1.1. Course facts.}

{\bf Instructor}: Leo Guibas\par

{\parskip 0in
\tb {\it Office:} Margaret Jacks 336\par
\tb {\it Office Hours:} TTh afternoons after class\par
\tb {\it Phone:} 497-4364 (Stanford) and 494-4437 (Xerox PARC)}
\par

\vskip 3 pt

{\bf TA}: Jorge Stolfi\par

{\parskip 0in
\tb {\it Office:} Margaret Jacks 450\par
\tb {\it Office Hours:} MWF 11:00 -- 12:00, in MJH 450\par
\tb {\it Phone:} 497-3088 (Stanford) and 328-0485 (home)}
\par

\vskip 3 pt

There is currently no textbook dealing specifically with Computational
Geometry. One has been promised for the near future by Franco
Preparata, who is updating and completing an unpublished text by 
Shamos (1974); preprints of some chapters may be available by the 
end of the quarter. A bibliography of the most important papers will be 
made available, and we will make a valiant effort to produce 
class notes covering the material given in the lectures.

There will be weekly pencil-and-paper homeworks, a midterm and a 
final exam (no programming assignments).

\sect{1.2 Overview of the field.}

{\it Computational Geometry} has only recently been recognized as 
a field of Computer Science;  the name itself was generally adopted 
around 1976-1977.  The field is currently undergoing rapid
growth; many fundamental questions are still 
far from being fully resolved. \par

Computational Geometry has lots of important applications; the list 
below shows some of the most common ones, and some geometrical 
problems that are characteristic of each application.\par

\vskip3pt plus10pt
\bu{\it Computer graphics}\par
{\parskip 0 in
\tb geometric sorting\par
\tb polygon intersection\par
\tb clipping }
\par

\vskip2pt plus10pt
\bu{\it Computer-aided design and manufacturing; automatic milling 
and robot control}\par
{\parskip 0 in
\tb union and intersection of surfaces\par
\tb clear-path determination}
\par

\vskip2pt plus10pt
\bu{\it VLSI design}\par
{\parskip 0 in
\tb union, intersection and near-contact of rectangles\par
\tb wire routing}
\par

\vskip2pt plus10pt
\bu{\it Pattern recognition, feature extraction and computer vision}\par
{\parskip 0 in
\tb fitting of geometrical objects to noisy data}
\par

\vskip2pt plus10pt
\bu{\it Statistics, operations research and numerical analysis}\par
{\parskip 0 in
\tb nearest-point determination\par
\tb triangulation}
\par

In addition, there is an extensive list of problems and applications 
that, although non-geometrical in origin and nature, can be better 
visualized and solved by recasting them in geometrical terms. For 
example, the geometrical equivalent of a database range-query problem 
(like ``find all employees with salary greater than $\$10000$ and age between 
30 and 40'') is the selection, from a collection of points in $n$-space, of
those that fall inside a given $n$-dimensional box.\par

On the other hand, it has been known since the time of Descartes 
that any geometrical problem can be recast in purely algebraic 
terms; it may seem unnecessary to have for such problems a special 
discipline, distinct from numerical calculus. Indeed, some problems 
in geometry are best solved by algebraic methods, like the computation 
of the area of a polygon; but it is equally true that most geometrical 
concepts and algorithms are best ``seen'' and studied and in their 
own framework.\par

Most of the fundamental problems and results of Computational Geometry 
have been studied well before the field was recognized as a discipline 
in itself. Actually, we can say that Computational Geometry is the 
most ancient branch of Computer Science: the constructions 
of Euclidean geometry are legitimate {\it algorithms}, constructed from 
a well-defined, finite set of elementary operations.

In fact, Euclidean geometry is where several of the key concepts 
of Computer Science were first introduced: the close relashionship 
between an algorithm and the proof of its correctness, the first 
examples of ``provably unsolvable'' problems (doubling the cube, 
trisecting the angle, squaring the circle), and so forth.  
Early in this century, the French mathematician Lemoine introduced (without 
much success) the 
idea of ``computational complexity'' of a geometrical construction, 
by counting the number of ``elementary'' steps it required. 
The work of other 19\th century geometers of the time (like Mohr and Mascheroni), 
who showed that the ruler and compass of ``classical'' geometry 
could be replaced by other sets of tools (compass alone, ruler and 
scale,  ruler and fixed-aperture compass, and so forth), is a 
close parallel to the theorems establishing equivalence 
of power for different flavors of Turing machines by simulation.\par 

Because of the long ``pre-history'' of the field and its large 
number of applications, the fundamental results and techniques 
of Computational Geometry are widely scattered in publications 
that range from highly abstract mathematics texts to  applications-oriented 
journals.\par

The goal of Computational Geometry is to collect and study all this 
material into the common framework of Analysis of Algorithms.  In 
particular, there seems to be a small set of
techniques and structures (say, less than 10) 
that have such a wide range of applications 
that they deserve to be called ``fundamental'', in the same sense 
balanced binary 
trees and sorting algorithms are fundamental for Combinatorial Algorithms in 
general. The convex hull and the Voronoi diagram are two of these 
basic concepts that we will study later on.\par

In this course we will be concerned mostly with planar problems 
and algorithms; we may refer to extensions for three and higher
dimensions, but usually without proofs and details. Due to time 
limitations, we will put more emphasis on points, straight lines 
and planes, rather than general curves and surfaces. Finally, we 
will not cover discrete (raster or pixel) geometry, which alone could 
provide enough material for a course. For a detailed (and 
optimistic) list of topics to be covered, see the course announcement.\par

\vfill\end(635)