\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