\documentclass[11pt,a4paper,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
\usepackage{textcomp}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{aecompl}
%----------------------------
%\usepackage[colorlinks,bookmarks,linkcolor=black,citecolor=black]{hyperref}
\usepackage{hyperref}
\hypersetup{colorlinks=false}
\usepackage{srcltx}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{graphicx}
\usepackage{subfig}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\def\@setaddresses{\par
  \nobreak \begingroup
\footnotesize
  \def\author##1{\nobreak\addvspace\bigskipamount}%
  \def\\{\unskip, \ignorespaces}%
  \interlinepenalty\@M
  \def\address##1##2{\begingroup
    \par\addvspace\bigskipamount\indent
    \@ifnotempty{##1}{(\ignorespaces##1\unskip) }%
    {\scshape\ignorespaces##2}\par\endgroup}%
  \def\curraddr##1##2{\begingroup
    \@ifnotempty{##2}{\nobreak\indent{\itshape Current address}%
      \@ifnotempty{##1}{, \ignorespaces##1\unskip}\/:\space
      ##2\par}\endgroup}%
  \def\email##1##2{\begingroup
    \@ifnotempty{##2}{\nobreak\indent{\itshape Endereço eletrônico}%
      \@ifnotempty{##1}{, \ignorespaces##1\unskip}\/:\space
      \ttfamily##2\par}\endgroup}%
  \def\urladdr##1##2{\begingroup
    \@ifnotempty{##2}{\nobreak\indent{\itshape URL}%
      \@ifnotempty{##1}{, \ignorespaces##1\unskip}\/:\space
      \ttfamily##2\par}\endgroup}%
  \addresses
  \endgroup
}
\makeatother

\def\({\left(}
\def\){\right)}
\def\<{\langle}
\def\>{\rangle}
\let\:\colon

\def\aa{{\mathtt A}}
\def\cc{{\mathtt C}}
\def\gg{{\mathtt G}}
\def\tt{{\mathtt T}}
\def\ZZ{{\mathbb Z}}
\def\RR{{\mathbb R}}
\def\FF{{\mathbb F}}
\let\:\colon
\def\bfx{\mathbf{x}}
\def\bfp{\mathbf{p}}
\def\Stanf{^\text{S}}

\def\Fat{\mathop{{\rm Fat}}\nolimits}

\usepackage{datetime}

\begin{document}
\onehalfspacing

\title[EP2 CCM128 1o.~semestre 2014]{%
  {\sl CCM128 Exercício-Programa 2}\\\medskip
   Retângulos vazios}
\author{Y.~Kohayakawa}
\address{Instituto de Matemática e Estatística, Universidade de São Paulo, Rua
  do Matão 1010, 05508--090~São Paulo, SP}
\email{yoshi@ime.usp.br}

\def\datename{Versão de}
%\date{\today, \currenttime.  Versão preliminar} 
\date{\today, \currenttime}

\maketitle
%\thispagestyle{empty}
\footskip=25pt

\noindent\textbf{Data de entrega:}\quad 12/5/2014 (23:55)

\section{Introdução e definições básicas}
Este EP trata de um problema de geometria computacional.  Consideremos
conjuntos finitos~$S$ de pontos do quadrado unitário~$I^2=I\times
I=[0,1]\times[0,1]$ e `retângulos abertos'~$R$ contidos em~$I^2$, isto
é, conjuntos da forma
\begin{equation}
  \label{eq:ret_def}
  R(x_1,x_2,y_1,y_2)=(x_1,x_2)\times(y_1,y_2)=\{(x,y)\in
  I^2\:x_1<x<x_2\text{ e }y_1<y<y_2\},
\end{equation}
onde~$x_1$, $x_2$, $y_1$ e~$y_2\in I$.  Dizemos
que~$R=R(x_1,x_2,y_1,y_2)$ \textit{evita}~$S$ se~$R\cap S=\emptyset$;
também dizemos que tal~$R$ é `vazio' (de pontos de~$S$).  O problema
que queremos resolver é o problema do \textit{maior retângulo vazio}
(MRV): \textit{dado~$S$, encontrar um retângulo~$R$ de maior área
  possível que evita~$S$}.  

A Figura~\ref{fig:1} mostra duas instâncias resolvidas.

\begin{figure}[here]
  \centering
  \subfloat[$|S|=200$; área do retângulo
  vazio: $0.03640834823302188$]%
  {\includegraphics[width=6cm]{figs/200-1}}
  \qquad
  \subfloat[$|S|=2000$; área do retângulo
  vazio: $0.007891822017010351$]%
  {\includegraphics[width=6cm]{figs/2000-0}}
  \caption{Duas instâncias resolvidas}%
  \label{fig:1}%
\end{figure}

\section{Objetivo principal}
\label{sec:objetivo}
Neste EP, você deve escrever um programa `eficiente' que resolve o MRV
para conjuntos~$S\subset I^2$ dados.  Estamos particularmente
interessados no caso em que~$S$ é gerado \textit{aleatoriamente}, com
cada elemento de~$S$ escolhido ao acaso de forma uniforme em~$I^2$,
independentemente de todos os outros pontos de~$S$.  (Veja uma breve
discussão sobre instâncias aleatórias na
Seção~\ref{sec:instancias_al}.)  Seu programa deve ser capaz de
resolver tais instâncias~$S$ com centenas ou milhares de pontos
rapidamente (esta exigência está formulada de forma vaga
propositadamente).

\section{Seu programa}
\label{sec:seu_prog}
É natural decompor seu programa em vários módulos.  Por exemplo, é
natural implementar classes para pontos, conjuntos de pontos e
retângulos.  

Ademais, você deve implementar um módulo de visualização, que exibe a
instância e a solução encontrada (isto é, um módulo que gera figuras
como aquelas na Figura~\ref{fig:1}).  

Você deve também implementar um módulo para executar o
\textit{doubling test}.  Você deve usar este módulo para estimar a
complexidade de tempo de seu algoritmo para resolver o~MRV em
instâncias aleatórias.  Não deixe de discutir sua conclusão (empírica)
sobre a complexidade de seu algoritmo em seu relatório.  Procure
também fazer uma análise teórica da complexidade de seu algoritmo.

Você deve também implementar um módulo que, dado~$N$, estima o valor
esperado da área do maior retângulo vazio relativo a um conjunto
aleatório~$S$ com~$|S|=N$.  Finalmente, você deve implementar um
módulo que gera um gráfico deste valor esperado em função de~$N$.

No que segue, discutimos os módulos que você deve implementar, dando
exemplos de seus usos (estes exemplos devem tornar mais claro o que é
pedido neste EP).

\subsection{\texttt{Point.java}, \texttt{PointSet.java},
  \texttt{Rectangle.java}}
\label{sec:basic_classes}
Essas classes devem implementar os tipos \verb|Point|, \verb|PointSet|
e \verb|Rectangle|.  Implemente as seguintes formas de execução de
\verb|PointSet|.  Para gerar um conjunto aleatório com~$N$ pontos ($N=6$): 
{\small
\begin{verbatim}
$ java-introcs PointSet -r 6
6
0.19079518105227067 0.7781257632978256
0.4974153326919968 0.2503665625736603
0.5213656070164971 0.38069973596554463
0.22754335354306854 0.6710899050769443
0.1754296870531391 0.36021400982688445
0.3817382183726922 0.3955423012618332
\end{verbatim}
} O conjunto gerado pode ser armazenado para ser processado
posteriormente:
{\small
\begin{verbatim}
$ java-introcs PointSet -r 6 > data.6
$ cat data.6
6
0.36669290177551617 0.4717504294232526
0.5483975883724658 0.5076621962517646
0.9544398399611626 0.3500417766273609
0.006611416732648867 0.235248480395164
0.4078041440144815 0.3870395237696017
0.07633625320490867 0.5961843373135058
$ java-introcs PointSet -i < data.6
Max area: 0.4547545804989615
\end{verbatim}
}

\subsection{\texttt{Visualize.java}}
\label{sec:Visualize}
Para resolver uma dada instância e fazer a ilustração da solução: 
{\small
\begin{verbatim}
$ java-introcs Visualize -i < data.6
\end{verbatim}
}
A execução acima deve gerar uma saída como na Figura~\ref{fig:2}.  
\begin{figure}[here]
  \includegraphics[width=6cm]{figs/data6-fig}
  \caption{Solução para o conjunto em \texttt{data.6}}%
  \label{fig:2}%
\end{figure}
Para gerar instâncias aleatórias com~$N$ pontos~$M$ vezes e exibir as
soluções graficamente ($N=800$ e~$M=10$):
{\small
\begin{verbatim}
$ java-introcs Visualize 800 10
\end{verbatim}
}
Para armazenar as figuras geradas por \verb|Visualize|, você deve
permitir o usuário a executar
{\small
\begin{verbatim}
$ java-introcs Visualize -i data-500 < data.500
\end{verbatim}
}\noindent
Nesta execução, devem ser gerados os arquivos \verb|data-500.jpg| e
\verb|data-500.txt|, com o primeiro contendo uma figura ilustrando a
solução e o segundo contendo a saída em formato texto (você pode
decidir quais informações colocar neste segundo arquivo, mas a área do
retângulo encontrado deve fazer parte).  Implemente também o seguinte
formato de execução: 
{\small
\begin{verbatim}
$ java-introcs Visualize 1000 3 random-1000
\end{verbatim}
}\noindent
Neste caso, devem ser gerados~$6$ arquivos (três com figuras e três
com a saída em formato texto).

\subsection{\texttt{DoublingTest.java}}
\label{sec:Doubling}
Para executar o \textit{doubling test} para estimar a complexidade de
seu algoritmo em instâncias aleatórias, o usuário deve poder fazer
{\small
\begin{verbatim}
$ java-introcs DoublingTest
      N    time ratio
     16    0.00 2.00
     32    0.01 4.50
     64    0.05 5.78
    128    0.20 3.79
  [...]
\end{verbatim}
}

\subsection{\texttt{AveArea.java} e \texttt{AreaPlot.java}}
\label{sec:plot}
Para estimar o valor esperado da área do maior retângulo vazio para
instâncias aleatórias com~$N$ pontos, o usuário poderá gerar tais
instâncias~$M$ vezes e calcular a média ($N=500$ e~$M=100$): {\small
\begin{verbatim}
$ java-introcs AveArea 500 100
Average = 0.023699853652082905
\end{verbatim}
} Por conveniência, denotemos por~$\mu(N)$ o valor esperado do maior
retângulo vazio para instâncias aleatórias com~$N$ pontos.  Lembre a
técnica usada em \verb|PercPlot.java| para gerar gráficos.  Use aquela
técnica para gerar gráficos como na Figura~\ref{fig:3}.  O gráfico na
Figura~\ref{fig:3} foi obtido executando-se {\small
\begin{verbatim}
$ java-introcs AreaPlot 500
\end{verbatim}
} 
%
\begin{figure}[here]
  \includegraphics[width=7cm]{figs/500-graph}
  \caption{Uma aproximação (experimental) do gráfico de~$\mu(N)$}%
  \label{fig:3}%
\end{figure}
% 
\noindent
Neste gráfico, o eixo~$x$ corresponde aos valores de~$N$, com~$0\leq
N\leq500$ (\verb|AreaPlot| foi executado com~$N=500$), enquanto que o
eixo~$y$ corresponde aos valores (estimados) de~$\mu(N)$.  O ponto
mais à esquerda no gráfico (que é~$(0,1)$) corresponde ao caso~$N=0$.
O ponto mais à direita (que é algo como~$(1,0.0236\dots)$) corresponde
ao caso~$N=500$.

Usando seu programa \verb|AreaPlot| ou programas semelhantes, você
consegue conjecturar como a função~$\mu(N)$ decai conforme~$N$ cresce?  

\subsection{Instâncias aleatórias}
\label{sec:instancias_al}
Seu EP deve ser capaz de resolver instâncias dadas (a serem lidas no
\verb|stdin|), mas também deve ser capaz de gerar e resolver
instâncias aleatórias.  As instâncias aleatórias devem ser geradas da
seguinte forma: dado~$N$, você deve gerar~$P_i$ ($0\leq i< N$)
uniformemente ao acaso no quadrado~$I^2$, usando
\verb|StdRandom.uniform()| (este método gera quantidades \verb|double|
em~$[0,1)$ e não em~$I=[0,1]$, mas você pode ignorar este fato).
Neste enunciado, quando falamos de \textit{instâncias aleatórias},
estamos sempre falando de instâncias geradas dessa forma.

\section{Desafio (Opcional)}
\label{sec:desafio}

Resolva o problema do \textit{maior disco vazio} (MDV):
\textit{dado~$S$, encontrar um disco aberto~$D$ de maior área possível
  que evita~$S$}.  Por simplicidade, neste problema, você deve
entender que~$S\subset I^2$ corresponde à instância
(infinita)~$\ZZ^2+S=\{(i,j)+P\:i,\,j\in\ZZ\text{ e }P\in S\}$ e que
estamos à procura de um disco~$D\subset\RR^2$ de área máxima que
evita~$S$ (nesta versão, a fronteira do quadrado unitário não impõe
restrições).

Este desafio pode ser entregue até o final do semestre.  Se você
pretende fazer este desafio, escreva para o monitor e para mim, para
que saibamos que você está trabalhando nele.

\subsection*{Observações} Seguem algumas observações importantes.

\small
\begin{enumerate}
\item \textit{Este EP é estritamente individual}.  Programas
  semelhantes receberão nota~$0$.
\item Seja cuidadoso com sua programação (correção, documentação,
  apresentação, clareza de código, etc).  A correção não é baseada
  apenas na correção de seu programa.
\item Comparem entre vocês o desempenho de seus programas.
\item Entregue seu EP no Paca.
\item Não deixe de incluir em seu material um \textit{relatório} para
  discutir seu EP: faça quaisquer comentários que você achar
  interessante e inclua exemplos de execuções de seu programa.
\end{enumerate}

\subsubsection*{Observação final}  Enviem dúvidas para a lista de discussão da
disciplina.

%\bibliographystyle{abbrv}
%\bibliography{refs_Teach}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% eval: (auto-fill-mode t)
%%% eval: (flyspell-mode t)
%%% eval: (LaTeX-math-mode t)
%%% TeX-master: t
%%% End:
