A procura de algoritmos para resolver problemas geom�tricos vem desde a �poca da antiguidade. (Algumas motiva��es pr�ticas para a busca por tais algoritmos foram os impostos sobre o uso da terra e as constru��es de edifica��es.) S�o bem conhecidas as constru��es geom�tricas de Euclides que usavam como instrumentos r�gua e compasso e consistiam de algumas opera��es primitivas que podiam ser realizadas com esses instrumentos. Um dos problemas algor�tmicos1 em geometria foi o chamado Problema de Apollonius (cerca de 200 A.C.) no qual tr�s circunfer�ncias arbitr�rias no plano eram dadas e pedia-se uma quarta circunfer�ncia que fosse tangente �s tr�s circunfer�ncias dadas. Euclides apresentou um algoritmo que resolve este problema.
Dentre todos os problemas algor�tmicos em geometria (usando constru��es geom�tricas de Euclides) um que atraiu grande aten��o foi o problema da constru��o de um pol�gono regular de n lados. Para alguns valores de n (e.g. n=3,4,5,6) a solu��o � conhecida desde a antiguidade. Entretanto, para hept�gonos regulares (n=7) prova-se que o problema n�o tem solu��o.2
Em 1902, Emile Lemoine introduziu uma medida de simplicidade para os algoritmos que usam as constru��es de Euclides. Esta medida � baseada no n�mero de opera��es primitivas realizadas pelo algoritmo. Para Lemoine o algoritmo mais simples � aquele que faz menos opera��es primitivas. (A solu��o de Euclides para o Problema de Apollonius requer 508 dessas opera��es enquanto que um algoritmo proposto por Lemoine requer menos do que duzentas.) Estava portanto introduzido em geometria um conceito que �, pelo menos em ess�ncia, o que hoje em dia chamamos de complexidade de um algoritmo.
Em geometria computacional tamb�m estamos interessados em desenvolver algoritmos eficientes para resolvermos problemas geom�tricos. Pelo que foi exposto acima vemos que n�o � algo novo. Com a diferen�a de que as opera��es primitivas usam um instrumento diferente da r�gua e do compasso: usam um computador. Um pouco mais precisamente, em geometria computacional estamos interessados em encontrar algoritmos eficientes, ou procedimentos computacionais, para resolver problemas geom�tricos. Muitos desses problemas tem sua origem em outras �reas como computa��o gr�fica, rob�tica, computer-aided design e processamento de imagens. No desenvolvimento de tais algoritmos s�o comumente utilizados resultados em: geometria euclidiana, combinat�ria, teoria dos grafos, estruturas de dados e an�lise de algoritmos.
Se a tese de M.I. Shamos em 1978 (cf. [20]) for aceita como o in�cio da geometria computacional (pelo menos da maneira como ela ser� tratada nesta disciplina3), ent�o a �rea tem apenas 19 anos. Apesar disso existem pelo menos 5 livros na �rea, 4 jornais.
De acordo com O'Rourke [17] (p�gina xi):
``...Not all open problems [em geometria computacional] are necessarily difficult; some are simply awaiting the requisite attention ...''.Este pode ser um bom motivo para ficarmos de olhos abertos durante a disciplina e talvez tentar fazer alguma contribui��o para a �rea. Divirtam-se!
[O que foi brevemente tratado nesta introdu��o pode ser encontrado no Cap�tulo 3 de [4], em [11] e no Cap�tulo 1 de [19].]