\documentclass[11pt, titlepage]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{amssymb}
\usepackage{graphics}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}

\title{Implementação de Dois Algoritmos para a Construção de Fecho
Convexo Bidimensional.}
\author{Rodrigo Nonamor Pereira Mariano de Souza\\Eduardo L. Siegfried
Blanco\\IME-USP}

\begin{document}
\maketitle
\tableofcontents
\newpage

\section{Introdução.}

Descrevemos neste relatório uma implementação e testes dos algoritmos
de Jarvis e Graham para a construção do fecho convexo de um conjunto
de pontos no plano.

O fecho convexo de um conjunto de pontos pode ser definido,
\emph{grosso modo}, como a fronteira do polígono que contém os pontos
do conjunto e cujos vértices são pontos do conjunto. Algoritmos para a
construção do fecho convexo fazem parte de uma área de pesquisa
conhecida como \emph{Geometria Computacional}, e começaram a ser
estudados nos anos 60. Há diversas aplicações desses algoritmos, por
exemplo, em robótica.

O algoritmo de Graham é ótimo, ou seja, sua complexidade é igual à
cota inferior do problema: $O(n \log n)$. O algoritmo de Jarvis é \emph{output
sensitive}, pois sua complexidade depende do número $h$ de arestas do
fecho: $O(hn) = O(n^2)$. O algoritmo de Jarvis é também conhecido na literatura
como \emph{Embrulho para Presente}, pela maneira como constrói o fecho
(para uma visualização da execução, basta imaginar que os pontos são
pregos e que o fecho é construído enrolando--se um barbante no
conjunto). Não serão feitas descrições dos algoritmos.

\section{Implementação.}

Os algoritmo foram implementados em C. Segue uma descrição dos
fontes:

\begin{itemize}
\item{\textbf{estruturas.h}:} Definição de macros e de tipos de
objetos geométricos.
\item{\textbf{primitivas.h}:} Protótotipos das primitivas Area2 e
Left.
\item{\textbf{fecho2.h}:} Protótipos das implementações dos
algoritmos. Os algoritmos de Graham e Jarvis são implementados,
respectivamente, nas funções \emph{graham} e \emph{jarvis}.
\item{\textbf{primitivas.c}:} Implementação das primitivas.
\item{\textbf{fecho2.c}:} Implementação dos algoritmos.
\item{\textbf{principal.c}:} Interface para a chamada dos algoritmos.
\end{itemize}

O programa é executado com

\begin{center}
\texttt{principal [npontos].}
\end{center}

Quando chamado sem argumentos, pede--se o fornecimento de um arquivo
contendo o conjunto de pontos. O formato do arquido de dados é o
seguinte:

\begin{center}
\begin{tabbing}
$\langle$Número \= de pontos$\rangle$ \\
$p_1.x$ \> $p_1.y$ \\
$p_2.x$ \> $p_2.y$ \\
$\vdots$ \\
$p_n.x$ \> $p_n.y$ \\
\end{tabbing}
\end{center}

\emph{Número de pontos} é inteiro, e indica o número de pontos do
conjunto. Os demais valores representam as coordenadas dos pontos, e
podem ser escritos com ponto flutuante.

O argumento opcional faz com que o programa gere um conjunto de pontos
de coordenadas aleatórias. O argumento é inteiro positivo, e indica o
número de pontos do conjunto a ser gerado.

O programa gera dois arquivos: \emph{graham.out} e
\emph{jarvis.out}, que contêm, respectivamente, o fecho encontrado
pelos algoritmos de Graham e de Jarvis.

A implementação é original, ou seja, não foi baseada em nenhuma outra
implementação existente, e é bastante simples, não incluindo possíveis
otimizações.

\section{Testes.}

Os testes consistiram na execução dos algoritmos para conjuntos de
pontos de coordenadas aleatórias. Foram testados conjuntos de tamanhos
variados e anotados os tempos de execução. Os tempos foram medidos com
o número de pulsos do relógio do processador\footnote{Os autores não
sabem que unidade de tempo é essa...}, obtidos com a função
\emph{clock} da biblioteca padrão \emph{time.h}. Seguem os resultados
obtidos:

\begin{center}
\begin{tabular}{|l|l|l|l|} \hline
N.o de pontos & Pontos no fecho & Tempo Alg. Jarvis (ticks) &
Tempo Alg. Graham (ticks) \\ \hline
100 & 8 & 30000 & 20000 \\ \hline
1000 & 18 & 90000 & 30000 \\ \hline
5000 & 19 & 350000 & 60000 \\ \hline
10000 & 24 & 840000 & 110000 \\ \hline
13000 & 24 & 1120000 & 130000 \\ \hline
15000 & 27 & 1420000 & 150000 \\ \hline
18000 & 24 & 1510000 & 190000 \\ \hline
20000 & 28 & 1950000 & 190000 \\ \hline
23000 & 27 & 2180000 & 240000 \\ \hline
25000 & 28 & 2460000 & 250000 \\ \hline
28000 & 26 & 2540000 & 280000 \\ \hline
30000 & 27 & 2850000 & 300000 \\ \hline
31000 & 27 & 2940000 & 320000 \\ \hline
\end{tabular}
\end{center}

Como pode--se perceber, o algoritmo de Graham se mostrou mais
eficiente que o de Jarvis em todas as instâncias. Um dado interessante
é a verificação de que o número de pontos do fecho cresce muito
lentamente com o tamanho da instância.

Na Figura~\ref{fig:graficotempo} há um gráfico dos resultados. Foram
também traçadas duas curvas, correspondentes às funções $c_1n\log_2 n$
e $c_2n\log_2 n$, onde $c_1$ e $c_2$ são constantes ($c_2 >
c_1$). Nota--se que o tempo de execução do algoritmo de Graham
acompanha a curva $c_1n\log_2 n$, confirmando o resultado teórico. O
algoritmo de Jarvis parece apresentar um crescimento ligeiramente
superior à curva $c_2n\log_2 n$.

\begin{figure}
\begin{center}
\includegraphics{grafico1.eps}
\end{center}
\caption{Tempo de Execução dos Algoritmos de Graham e Jarvis.}
\label{fig:graficotempo}
\end{figure}

\end{document}
