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].]