\documentclass{article}
%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

\usepackage{epsfig}

\title{Geometria Computacional\\
  Fecho Convexo Planar}

\author{Alexis S. L. Carvalho}

\begin{document}

\maketitle

\section{Introdução}

O problema do fecho convexo planar consiste de, dado um conjunto
finito de pontos no plano, encontrar o polígono convexo com menor área
que inclui todos esses pontos.

No projeto descrito nesse relatório, foram implementados alguns
algoritmos para esse problema. Como exemplo de aplicação, também foi
implementado um algoritmo que determina o diâmetro de um conjunto de
pontos.

\section{Implementação}

Como o objetivo primordial desse projeto é permitir a visualização de
algoritmos e permitir a comparação entre eles, as implementações
realizadas não são ótimas: diversas otimizações que dificultariam o
entendimento ou a visualização de um algoritmo não foram realizadas.

A implementação foi feita na linguagem Python, e existem três
\emph{front-ends}: 
\begin{itemize}
\item \texttt{tkgeocomp.py}: usa Tk para a interface gráfica;
\item \texttt{ggeocomp.py}: usa Gtk+/GNOME para a interface gráfica;
\item \texttt{cligeocomp.py}: modo texto, para poder ser usado em scripts.
\end{itemize}

O programa foi testado em Python 1.5.2 e 2.1, usando gnome-python
1.4.1 .

Foram implementados os seguintes algoritmos:
\begin{itemize}
\item Graham
\item Embrulho para Presente
\item Quickhull
\item Incremental
\item Incremental Probabilístico
\item Mergehull
\item Algoritmo ótimo proposto por Chan em \cite{chan}
\item Algoritmo ótimo proposto por Bhattacharya e Sen em \cite{bhatta}
\end{itemize}

Os dois últimos algoritmos possuem complexidade de tempo $O(n \log h)$
(pior caso e complexidade esperada, respecivamente), onde $n$ é o
número de pontos na entrada, e $h$ é o número de vértices no fecho
convexo. Como Kirkpatrick e Seidel demonstraram em \cite{kirk} uma
cota inferior de $O(n \log h)$ para esse problema quando tanto a
entrada quanto a saída são levadas em conta, esses dois algoritmos são
ótimos.

Os algoritmos de Graham e Mergehull são ótimos quando se considera
apenas a entrada --- complexidade de tempo $O(n \log n)$. Quickhull
possui complexidade de tempo média $O(n \log n)$ e $O(n^2)$ no pior
caso. Incremental Probabilístico possui complexidade esperada $O(n
\log n)$. Embrulho para Presente executa em tempo $O(nh)$ e o
algoritmo Incremental em tempo $O(n^2)$.

\section{Utilitários}

No diretório \texttt{utils} existem diversos \emph{scripts} que geram
pontos com coordenadas aleatórias, distribuídos uniformemente:
\begin{itemize}
\item em uma caixa (ou seja, um quadrado)
\item em uma circunferência
\item em um círculo
\item em um anel
\item em uma espiral
\item de tal forma que o fecho convexo possua $h$ vértices, para algum
  $h$ fornecido pelo usuário
\end{itemize}

Esses \emph{scripts} foram usados para gerar os arquivos de entrada
usados para testar o programa.

\section{Comparações}

Nos gráficos abaixo, o eixo das abcissas pode representar ou o número
de pontos na entrada, ou o número de vértices no fecho convexo. O eixo
das ordenadas representa sempre o número de operações primitivas
(cálculos de área) realizados pelos algoritmos.

``Gift'' é o algoritmo Embrulho para Presente, ``bhatta\_sen'', o
algoritmo proposto por Bhattacharya e Sen, ``chan'', o proposto por
Chan e ``incr\_prob'' é o algoritmo Incremental Probabilístico.

\subsection{Uniforme em uma circunferência}
O número de vértices no fecho convexo é máximo.

\begin{figure}[ht]
  \epsfig{file=circ.eps, width=\textwidth}
  \caption{\label{fig:circ1}Pontos em uma circunferência}
  
\end{figure}

\begin{figure}[ht]
  \epsfig{file=circ-2.eps, width=\textwidth}
  \caption{\label{fig:circ2}Pontos em uma circunferência}
\end{figure}

Esse é o pior caso de alguns algoritmos \emph{output-sensitive}.
A figura \ref{fig:circ1} permite visualizar o comportamento quadrático
dos algoritmos Embrulho para Presente e Incremental.

A figura \ref{fig:circ2} mostra que os algoritmos de Graham e
Mergehull, que não são \emph{output-sensitive}, realizam menos
operações nesse caso. 

\subsection{Uniforme em uma caixa}
O número de vértices cresce lentamente em comparação com o número de
pontos.

\begin{figure}[ht]
  \begin{center}
    \epsfig{file=box.eps, width=\textwidth}
    \caption{\label{fig:box} Pontos em uma caixa}
  \end{center}
\end{figure}

A figura \ref{fig:box} mostra que os algoritmos ``bhatta\_sen'' e
Quickhull são os mais eficientes nesse caso, seguidos de perto pelo
Mergehull.

\subsection{Número de vértices no fecho convexo é constante}

\begin{figure}[ht]
  \begin{center}
    \epsfig{file=c2.eps, width=\textwidth}
    \caption{\label{fig:vconst} Número de vértices na saída é constante}
  \end{center}
\end{figure}

Novamente, Quickhull e ``bhatta\_sen'' são os mais eficientes. Por
causa do número reduzido de vértices no fecho, Embrulho para Presente
e ``chan'' são comparáveis ao Mergehull. Graham e Incremental
Probabilístico são comparáveis entre si, mas bem menos eficientes que
os outros. Incremental é o pior.

\subsection{Número de pontos constante; número de vértices na saída
  aumenta}
As figuras \ref{fig:nconst1} e \ref{fig:nconst2} permitem ver claramente
a sensibilidade à saída de alguns algoritmos:

Embrulho para Presente e Incremental crescem rapidamente à medida que
o número de vértices no fecho aumenta.

``Chan'' dá saltos quando o número de vértices chega a 16, 64 e 256.

Incremental Probabilístico fica aproximadamente constante, com um
pequeno aumento no final, que talvez possa ser explicada pela randomização do
algoritmo. 

Quickhull e ``bhatta\_sen'' crescem \emph{lentamente} com o número de
vértices.

Graham e Mergehull permanecem constante --- na verdade até diminuem um
pouco.

\begin{figure}[ht]
  \epsfig{file=n2.eps, width=\textwidth}
  \caption{\label{fig:nconst1} Número de pontos constante}
\end{figure}

\begin{figure}[ht]
  \epsfig{file=n2-2.eps, width=\textwidth}
  \caption{\label{fig:nconst2} Número de pontos constante}
\end{figure}


\section{Observações}

Se levarmos em conta apenas as figuras apresentadas, podemos concluir
que ``bhatta\_sen'' é mais eficiente que Quickhull e que Mergehull é
bem mais eficiente que Graham.

Mas as figuras apresentadas \emph{não} apresentam o tempo (em segundos)
que cada algoritmo levou. Se levarmos em conta apenas esse tempo,
vemos que Quickhull é um pouco mais rápido que 
``bhatta\_sen'' nos casos apresentados, e que Graham, em geral, é mais
rápido do que Mergehull.

Nos algoritmos randomizados (``bhatta\_sen'' e Incremental Probabilístico), as
medidas apresentadas são as médias obtidas depois de rodar cada teste 4 vezes.

\begin{thebibliography}{99}
  
\bibitem[chan96]{chan} T. M. Chan. \textsl{Optimal Output-Sensitive Convex
    Hull Algorithms in Two and Three Dimensions}. Discrete \&
    Computational Geometry, 16:361-368,
    1996. \texttt{http://http://citeseer.nj.nec.com/256494.html} 
    
  \bibitem[bs97]{bhatta} B. K. Bhattacharya e S. Sen. \textsl{On a Simple,
    Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull 
    Algorithm}. J. Algorithms, 25:177--193,
    1997. \texttt{http://citeseer.nj.nec.com/206645.html}  

  \bibitem[ks86]{kirk} D. G. Kirkpatrick e R. Seidel. \textsl{The ultimate
 planar convex hull algorithm?} SIAM Journal of Computing,
 15:287--299, 1986. 
\end{thebibliography}
\end{document}


