\documentclass[a4paper,10pt,twoside]{article}
\usepackage{amssymb,latexsym,amsmath}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel} 
\usepackage{epsfig} 
\usepackage{epstopdf} %pacotes para carregar imagens em .eps
\usepackage{indentfirst} 
\usepackage{setspace} %pacote para formatar os espaços de margem e entre textos
\usepackage{multirow}
\usepackage{graphicx}
\bibliographystyle{acm}
\pagestyle{myheadings}

%definindo a tamanho dos espaços
\setlength{\topmargin}{1.5cm}
%\setlength{\topskip}{0.3in}
\setlength{\textheight}{20.6cm}
\setlength{\textwidth}{14cm}
\setlength{\oddsidemargin}{1.5cm}
\setlength{\evensidemargin}{1.5cm}



\newtheorem{teorema}{Teorema}
\newtheorem{corolario}[teorema]{Corol\'ario}
\newtheorem{proposicao}[teorema]{Proposi\c c\~ao}
\newtheorem{lema}[teorema]{Lema}
\newtheorem{definicao}[teorema]{Defini\c c\~ao}
\newtheorem{observacao}[teorema]{Observa\c c\~ao}
\newtheorem{exemplo}[teorema]{Exemplo}


\begin{document}

%cria o cabeçalho das páginas com nome da revista e dos autores
\markboth{Revista Ciências Exatas e Naturais, Vol.XX, nºX, Jul/Dez, 201X}{\emph{Autor 1 e Autor 2}}

\begin{center}
%Capa

%Titulo e titulo traduzido
\vspace{-2.5cm}
{\large \textbf{Diagrama de Voronoi nas métricas Euclidiana e do táxi: Uma exploração em GeoGebra.}}\\
\vspace{1cm}
{\large \textbf{Voronoi Diagram in Euclidian and Taxicab Metric: An exploration using GeoGebra.}}\\
\vspace{1cm}

%Autores
\textbf{Autor 1}\\
Universidade 1\\
\emph{email1}\\
\vspace{0.5cm}
\textbf{Autor 2}\\
Universidade 2\\
\emph{email2}\\


\end{center}

\thispagestyle{empty} %Não enumera a capa


\noindent \textbf{Resumo:} 
Este trabalho apresenta uma exploração do conceito de diagrama de Voronoi na métrica Euclidiana e na métrica do táxi com ajuda do ambiente de geometria dinâmica GeoGebra. São descritas visualizações dinâmicas para alguns resultados teóricos relacionados ao diagrama de Voronoi na métrica Euclidiana, assim como ilustrações dos conceitos de táxi-circunferência e táxi-mediatriz. Finalmente é implementado um procedimento para a representação das regiões de influência do diagrama de Voronoi na métrica do táxi.\\

%-------------------------------------------------------------------------
%Inicial minúscula; Separação por ponto e vírgula; Ponto final.
\noindent {\bf Palavras-chave:} diagrama de Voronoi; métrica Euclidiana; métrica do táxi; GeoGebra.\\

%--------------------------------------------------------------------------

\noindent \textbf{Abstract:} 
This work presents an exploration of the Voronoi diagram in Euclidean and Taxicab metrics using the dynamic geometry environment GeoGebra. Using  dynamic visualizations, some theoretical results related to Voronoi diagram in Euclidean metric are illustrated  as well as the concepts of taxi-circumference and taxicab-bisector. Finally, a procedure is implemented to represent the regions of influence of the Voronoi diagram in the taxicab metric.\\

%-------------------------------------------------------------------------
%Inicial minúscula; Separação por ponto e vírgula; Ponto final.
\noindent {\bf Key words:} Voronoi diagram; Euclidian metric; táxicab metric; GeoGebra.

\section{Introdução}

A no\c{c}\~ao de diagrama de Voronoi de um conjunto de pontos $P$, pode ser relacionada à divisão do plano em um conjunto de regiões de influência,  cada uma determinada pela \textit{proximidade} entre os pontos da região e os pontos do conjunto $P$. As seguintes definições formalizam esta ideia:

{\definicao\label{celula} Dado um conjunto $P=\lbrace{p_{1}, p_{2}, ...,p_{n}}\rbrace$ de pontos  e uma métrica $d$ em $\mathbb R^2$, a \textbf{c\'elula de Voronoi $V_d(p_i)$} \'e definida como

$$V_d(p_i)=\{q \in \mathbb R^2:d(q,p_i)\leq d(q,p_j)\,\, \text{para}\,\,j=1,\ldots,n\}.$$
}

Caso não haja lugar a equívocos em relação à métrica, será usada a notação $V(p_i)$ no lugar de $V_d(p_i)$. A seguinte definição introduz o conceito de diagrama de Voronoi de um conjunto de pontos.

 {\definicao\label{definicao}  O \textbf{diagrama de Voronoi} de $P=\lbrace{p_{1}, p_{2}, ...,p_{n}}\rbrace$, denotado por $Vor(P)$ é definido como a uni\~ao das fronteiras de todas as c\'elulas de Voronoi $V(p_i)$ correspondentes aos pontos do conjunto $P$.}


Assim, cada célula de Voronoi $V(p_i)$ é o conjunto dos pontos que est\~ao mais pr\'oximos ou à mesma distância de $p_{i}$ do que de qualquer outro ponto de $P$ e o diagrama de Voronoi $Vor(P)$ é a união das fronteiras de todas as células de Voronoi. As Figuras \ref{Figura11} e \ref{Voro1} ilustram estes conceitos considerando a métrica euclidiana.


\begin{figure}[!ht]
\centering
\includegraphics[height=6cm]{Figura11.eps}
\caption{C\'elula de Voronoi $V(p_i)$}%legenda da figura
\label{Figura11}
\end{figure}

\begin{figure}[!ht]
\centering
\includegraphics[height=6cm]{Voro1.eps}
\caption{Diagrama de Voronoi $Vor(P)$}
\label{Voro1}
\end{figure}


É possível encontrar na literatura definições diferentes das aqui apresentadas. Em \cite{okabe2009spatial} por exemplo, o diagrama de Voronoi é definido como o conjunto das células e não como a união das fronteiras. Em \cite{de2008computational} as células são definidas usando a desigualdade estrita $d(q,p_{i})<d(q,p_{j})$ no lugar da desigualdade $d(q,p_{i})\leq d(q,p_{j})$. Neste trabalho as definições apresentadas seguem as consideradas em \cite{notasIMPA}.

Segundo \cite{voronoi}, as primeiras apresenta\c{c}\~oes formais do conceito do diagrama de Voronoi aparecem em trabalhos de Peter Gustav Lejeune Direchlet (1805-1859) e George Fedoseevich Voronoy (ou Voronoi) (1868-1908). Em 1854, o m\'edico brit\^anico John Snow utilizou uma ideia similar ao diagrama de Voronoi, para concluir que maioria das pessoas que morreram na epidemia de c\'olera em Soho, distrito de Londres, moravam  mais perto da bomba de \'agua de Broad Street do que de qualquer outra bomba, mostrando assim a rela\c{c}\~ao entre a \'agua consumida e o surto da doen\c{c}a. Este fato \'e considerado como o in\'icio da epidemiologia moderna \cite{johnson2008mapa}.
 
Estruturas relacionadas ao diagrama de Voronoi aparecem em v\'arias \'areas do conhecimento: astronomia, arqueologia, planejamento urbano, f\'isica, fisiologia, estudo de epidemias, ecologia, entre outras \'areas \cite{okabe2009spatial}. O diagrama de Voronoi também é estudado na área de geometría computacional \cite{notasIMPA}. 

Este trabalho considera o uso do ambiente de geometria dinâmica GeoGebra para a exploração do conceito de diagrama de Voronoi na métrica Euclidiana e na métrica do táxi. Serão descritas algumas construções dinâmicas para ilustrar resultados teóricos relacionados ao diagrama na métrica Euclidiana, assim como visualizações dos conceitos de táxi-circunferência e táxi-mediatriz. Finalmente é considerado um procedimento para a representação das regiões de influência do diagrama de Voronoi na métrica do táxi. 

\section{Diagrama de Voronoi na métrica Euclidiana}

A determinação explicita do diagrama de Voronoi na métrica euclidiana, pode ser feita usando algum dos vários algoritmos descritos na literatura  \cite{okabe2009spatial, de2008computational, notasIMPA} mas quando é considerado um conjunto com um, dois ou três pontos, é possível determinar o diagrama de Voronoi de forma simples.

\subsection{ Diagrama de Voronoi para um, dois ou três pontos}

Quando houver apenas um ponto, a célula de Voronoi ser\'a o plano todo e o diagrama de Voronoi sera vazio. Para dois pontos $A$ e $B$, basta construir a mediatriz do segmento $\overline{AB}$. Sobre a mediatriz de $\overline{AB}$ est\~ao os pontos que ficam a mesma dist\^ancia dos dois pontos e as células de Voronoi s\~ao justamente os semiplanos fechados definidos pela mediatriz. O diagrama de Voronoi correspondente resulta ser a própria mediatriz dos pontos.

Para três pontos, tem-se dois possíveis casos: pontos colineares ou não colineares. Consideremos primeiro o caso do diagrama de Voronoi para tr\^es pontos $A$, $B$, e $C$ n\~ao colineares.  Inicialmente s\~ao determinadas as mediatrizes dos segmentos $\overline{AB}$, $\overline{BC}$ e $\overline{CA}$ como ilustrado na Figura \ref{Figura2}.



\begin{figure}[!ht]
\centering
\includegraphics[height=6cm]{Figura2.eps}
\caption{Constru\c{c}\~ao das mediatrizes.}
\label{Figura2}
\end{figure}

O ponto de encontro das mediatrizes é um ponto que esta a mesma distância de três pontos e ser\'a chamado de v\'ertice do diagrama de Voronoi. Note que este ponto é justamente o circuncentro do triângulo $ABC$. Para determinar como ser\~ao as células de Voronoi para cada ponto, note que sobre a mediatriz do segmento entre dois pontos, há pontos que estão mais próximos do terceiro ponto do que dos dois pontos iniciais, assim esses pontos pertencem à região de influência do terceiro ponto. Basta eliminar então esses pontos em cada mediatriz para obter a representação adequada das células de Voronoi. Note por exemplo que para o ponto de influ\^encia $A$ na Figura \ref{Figura2}, a parte \textit{inferior à esquerda} da mediatriz do segmento $\overline{BC}$ ser\'a desconsiderada, pois estes pontos est\~ao mais pr\'oximos do ponto $A$ e portanto pertencem a regi\~ao de influ\^encia de $A$. O mesmo ser\'a feito com as outra mediatrizes conforme a Figura \ref{Figura3}:



\begin{figure}[!ht]
\centering
\includegraphics[height=6cm]{Figura3.eps}
\caption{Elimina\c{c}\~ao dos segmentos que \textit{invadem} as regi\~oes de influ\^encia.}
\label{Figura3}
\end{figure}


A figura restante, ap\'os a elimina\c{c}\~ao dos segmentos, ser\'a o diagrama de Voronoi para estes tr\^es pontos no plano:

\begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{Figura4.eps}
\caption{Diagrama de Voronoi para os pontos não colineares $A$, $B$ e $C$.}
\label{Figura4}
\end{figure}


Se os três pontos forem colineares, o diagrama de Voronoi sera formado por retas (mediatrizes) paralelas. Isto será enunciado e ilustrado no Teorema \ref{segmentossemirretas}. Todas as figuras consideradas na discussão anterior foram geradas usando GeoGebra, mas é possível usar esta ferramenta para uma exploração mais dinâmica de outras propriedades do diagrama de Voronoi.

\subsection{Usando GeoGebra  para explorar o diagrama de Voronoi na métrica Euclidiana}

O diagrama de Voronoi na métrica Euclidiana pode ser gerado em GeoGebra usando os comandos \textbf{DiagramaDeVoronoi} ou \textbf{Voronoi} como é ilustrado na Figura \ref{ComVor}.

 
 \begin{figure}[!ht]
 \centering
\framebox{\includegraphics[height=6cm]{Teste1.eps}}
\caption{Diagrama de Voronoi na métrica Euclidiana em GeoGebra.}
 \label{ComVor}
\end{figure}


A seguir vamos explorar algumas propriedades do diagrama de Voronoi na métrica euclidiana. As demonstrações das propriedades que serão consideradas podem ser encontradas em \cite{notasIMPA} ou \cite{scaburi:2016}.


{\teorema Seja $P=\lbrace{p_{1}, p_{2}, ...,p_{n}}\rbrace$ pontos no plano. Se todos os pontos forem colineares o $Vor(P)$ consiste em $n-1$ linhas paralelas. Caso contr\'ario, $Vor(P)$ \'e formado por segmentos de reta ou semirretas.\label{segmentossemirretas}}\\

Este resultado pode ser ilustrado com facilidade em GeoGebra manipulando diretamente os pontos considerados e o comando \textbf{Voronoi} ou com ajuda de um controle deslizante.

\begin{figure}[h]
 \centering
\includegraphics[height=5cm]{Prop1.eps}\\
\includegraphics[height=5cm]{Prop2.eps}\\
\includegraphics[height=5cm]{Prop3.eps}\\
\caption{Diagrama de Voronoi: Pontos Não Colineares e Colineares.}
 \label{Prop1}
\end{figure}

\newpage

Na Figura \ref{Prop1}, note como quanto mais próximo os pontos encontram-se da reta $f$, os segmentos de reta no diagrama de Voronoi vão mudando sua inclinação até ser retas paralelas. Uma construção dinâmica correspondente  pode ser acessada em https://ggbm.at/c9E3hgjG.

 

Os pr\'oximos  tr\^es teoremas permitem determinar, através de circunferências, se um ponto qualquer do plano é ponto interior de alguma c\'elula, está sobre uma \'unica aresta, ou é um dos vértices do diagrama de Voronoi de um conjunto de pontos $P=\{p_1,p_2,\dots,p_n\}$. Para estabelecer a classificação, dado um ponto $p\not\in{P}$ será usada a notação $ C_p$ para denotar um \textbf{c\'irculo com centro $p$ que não tem nenhum dos pontos do conjunto $P$ no seu interior}.

{\teorema Um ponto $p$ \'e um ponto interior de $V(p_i)$ se e somente se existe um c\'irculo $C_p$ tal que $p_i$ é único  ponto de $P$ na fronteira de $C_p$.\label{unicoponto}}\\


 \begin{figure}[h]
 \centering
\includegraphics[height=6cm]{Figura16.eps}
\caption{Ponto interior a $p_i$.}
\label{Figura16}
\end{figure}

Note na Figura \ref{Figura16}, que a circunferência em destaque, é a única com centro em $p$, que possui um ponto de $P$ na fronteira e nenhum ponto de $P$ no interior. O seguinte resultado carateriza os pontos que pertencem exatamente a duas células de Voronoi, isto é, são pontos no interior relativo de uma das arestas e não são vértices.


{\teorema Um ponto $p$ \'e um ponto interior da aresta $V(p_i)\cap V(p_j)$ se, e somente se, existe um c\'irculo $C_p$ tal que exatamente os pontos $p_i$ e $p_j$ de $P$, estão na fronteira de $C_p$.\label{doispontos}}\\

 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{Figura17.eps}
\caption{Pontos interiores a aresta de Voronoi.}
\label{Figura17}
\end{figure}

Na Figura \ref{Figura17}, é ilustrado o fato de que para um ponto $p$ no interior da aresta é possível construir um círculo $C_p$ com exatamente os pontos $p_i$ e $p_j$ na fronteira de $C_p$. A figura também ilustra o fato de que esta mesma propriedade é satisfeita por pontos $p'$ e $p''$ sobre a aresta que estejam suficientemente \textit{próximos} de $p$.

\newpage

{\teorema Um ponto $p$ \'e um v\'ertice de Voronoi se, e somente se existe um c\'irculo $C_p$ tal que há pelo menos tr\^es pontos de $P$ na fronteira de $C_p$.\label{trespontos}}\\

 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{teorema14.eps}
\caption{Ponto sobre o v\'ertice de Voronoi.}
\label{teorema14}
\end{figure}


Na Figura \ref{teorema14}, é ilustrado o fato de que para um ponto $p$ que seja vértice do diagrama é possível construir um círculo $C_p$ com três ou mais pontos de $P$ na fronteira. Note que os pontos $p'$ e $p''$ \textit{próximos} de $p$, não tem esta propriedade.


Além de usar GeoGebra para a construção de gráficos, é possível utilizar as ferramentas de GeoGebra para ilustrar dinamicamente os três teoremas anteriores simultaneamente.  Um exemplo de uma construção dinâmica simples neste sentido pode ser encontrada em https://ggbm.at/JpnqZnPr.


O seguinte resultado, carateriza as células de Voronoi em termos do fecho convexo do conjunto $P$.

{\teorema A c\'elula de Voronoi $V(p_i)$ \'e ilimitada se, e somente se, $p_i$ est\'a na fronteira do fecho convexo de $P$.\label{teoremafechoconvexo}}\\

A demonstração deste resultado utiliza os teoremas anteriores de caraterização de pontos via circunferências \cite{notasIMPA}. É possível utilizar ferramentas básicas do GeoGebra para ilustrar diversas partes da demonstração \cite{scaburi:2016} ou construir uma ilustração dinâmica do resultado. Um exemplo de uma construção dinâmica neste sentido pode ser encontrada em https://ggbm.at/PdBm5BvQ.


 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{Voronoi3.eps}
\caption{Células de Voronoi e Fecho Convexo de $P$.}
\label{Voronoi3}
\end{figure}


\section{Métrica do Táxi}

Nesta seção vamos considerar a métrica do táxi. A métrica ou distância do t\'axi (também conhecida como métrica de Manhattan ou métrica $L_1$) $d_T$ entre dois pontos $A=(x_a, y_a)$ e $B=(x_b, y_b)$ \'e definida como 

\begin{equation}
d_T(A,B)= |x_a-x_b|+|y_a-y_b|
\label{defitaxi}
\end{equation}

 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{taxidistancia.eps}
\caption{Dist\^ancia ou m\'etrica do t\'axi.}
\label{taxidistancia}
\end{figure}


O nome de métrica do táxi é associado a esta métrica, pois numa região com ruas sempre paralelas ou ortogonais entre si, a distância total percorrida para ir de táxi do ponto $A$ ao ponto $B$ é igual a soma da distância percorrida em deslocamentos \textit{horizontais} mais a soma das distâncias percorridas em deslocamentos \textit{verticais}. Mas no plano, esta soma é justamente a soma definida na Equação  \ref{defitaxi} como é ilustrado na Figura \ref{taxidistancia}. Nosso objetivo final é utilizar GeoGebra para visualizar o diagrama de Voronoi de um conjunto de pontos na métrica do táxi, mas como não existe uma ferramenta pronta em GeoGebra para este propósito, na seção seguinte será desenvolvido um procedimento de representação aproximado. Para entender adequadamente este procedimento, nesta seção serão considerados os conceitos correspondentes à circunfer\^encia e mediatriz entre dois pontos na métrica do táxi e com ajuda do GeoGebra, serão exploradas algumas das suas características. Mais detalhes dos conceitos e demonstrações dos resultados considerados ao longo desta seção podem ser encontrados em \cite{scaburi:2016, rpm50a}.


\subsection{T\'axi-Circunfer\^encia}

A t\'axi-circunfer\^encia de centro $C$ e raio $r$ \'e o lugar geom\'etrico dos pontos no plano que na métrica do táxi distam $r$ unidades do ponto  $C=(x_c, y_c)$. Assim, uma \textit{t\'axi-circunfer\^encia} de raio $r$ e centro $C=(x_c, y_c)$ \'e formada pelos pontos $(x,y)$ que solucionam a equa\c{c}\~ao: 
\begin{equation}
|x-x_c|+|y-y_c|=r.
\label{equacaotaxicircunferencia}
\end{equation}

A seguinte proposi\c{c}\~ao caracteriza este lugar geom\'etrico.

{\proposicao\label{tcircunferencia} A t\'axi-circunfer\^encia de centro $C=(x_c, y_c)$ e raio $r$ \'e  o \textit{quadrilátero} de v\'ertices  $(x_c, y_c+r)$, $(x_c+r, y_c)$, $(x_c, y_c-r)$ e $(x_c-r, y_c)$. \label{proptaxicircunferencia}}


 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{taxicircunferencia.eps}
\caption{Táxi-circunfer\^encia.}
\label{taxicircunferencia}
\end{figure}

A representação gráfica de uma táxi-circunferência também pode ser obtida em GeoGebra utilizando a expressão \ref{equacaotaxicircunferencia} como é ilustrado na Figura \ref{TaxiCircGeo}

 \begin{figure}[!ht]
 \centering
\framebox{\includegraphics[height=6cm]{TaxiCircGeo.eps}}
\caption{Táxi-circunfer\^encia em GeoGebra.}
\label{TaxiCircGeo}
\end{figure}


\subsection{T\'axi-mediatriz}

A mediatriz entre os pontos $A$ e $B$ (ou mediatriz do segmento $\overline{AB}$) \'e definida como o lugar geom\'etrico dos pontos $P$ tais que $d(P,A)$ \'e igual a $d(P,B)$. Considerando a defini\c{c}\~ao da m\'etrica do T\'axi, para $P=(x,y)$, $A=(x_a, y_a)$ e $B=(x_b, y_b)$ temos que $P$ pertence \`a t\'axi-mediatriz de $\overline{AB}$ se, e somente se

\begin{equation}
|x-x_a|+|y-y_a|=|x-x_b|+|y-y_b|.
\label{taximediatriz}
\end{equation}


Em princípio, parece natural usar diretamente a expressão anterior para gerar em GeoGebra a táxi-mediatriz entre dos pontos, no entanto, veremos que esta implementação direta pode produzir uma representação um tanto confusa em certos casos. Nas Figuras \ref{MediatrizGeo1} e \ref{MediatrizGeo2} é ilustrado o uso direto da expressão  \ref{taximediatriz}  para gerar a representação da táxi-mediatriz em GeoGebra. 
  
 \begin{figure}[!ht]
 \centering
\framebox{\includegraphics[height=6cm]{MediatrizGeo1.eps}}\\
\caption{Táxi-Mediatriz em GeoGebra.}
\label{MediatrizGeo1}
\end{figure}

Note que, dependendo da posição relativa entre os pontos $A$ e $B$, a t\'axi-mediatriz entre  $A$ e $B$ pode ou não ser igual à mediatriz na métrica Euclidiana. Na Figura \ref{MediatrizGeo1} a táxi-mediatriz coincide com a mediatriz na métrica Euclidiana mas aa Figura \ref{MediatrizGeo2}, a táxi-mediatriz é formada por um segmento de reta unido a dois semirretas. A representação específica dependerá da inclinação $m$ entre os pontos $A$ e $B$. 
\begin{figure}[!ht]
 \centering
\framebox{\includegraphics[height=6cm]{MediatrizGeo2.eps}}\\
\caption{Táxi-Mediatriz em GeoGebra.}
\label{MediatrizGeo2}
\end{figure}

Se usamos diretamente a expressão  (\ref{taximediatriz}) para gerar a representação da táxi-mediatriz no caso em que esta inclinação é igual a $1$ ou $-1$ o resultado em GeoGebra pode parecer confuso, como sugerem as Figuras \ref{MediatrizGeo3} e \ref{MediatrizGeo4}. 


 \begin{figure}[!ht]
 \centering
\framebox{\includegraphics[height=6cm]{MediatrizGeo3.eps}}\\
\caption{Táxi-Mediatriz em GeoGebra para $m=1$.}
\label{MediatrizGeo3}
\end{figure}



 \begin{figure}[!ht]
 \centering
\framebox{\includegraphics[height=6cm]{MediatrizGeo4.eps}}\\
\caption{Táxi-Mediatriz em GeoGebra para $m=-1$.}
\label{MediatrizGeo4}
\end{figure}


Sem nenhum resultado teórico adicional, as representações apresentadas nas Figuras  \ref{MediatrizGeo3} e \ref{MediatrizGeo4} são no mínimo confusas e podem até parecer fruto de algum erro. A implementação direta e simples da equação da táxi-mediatriz em GeoGebra, não permite identificar adequadamente o que acontece com a táxi-mediatriz quando $m=1$ ou $m=-1$, como pode ser verificado na construção dinâmica disponível em https://ggbm.at/RVCjwEjB. A seguir, serão apresentados os resultados teóricos que estabelecem adequadamente as caraterísticas da táxi-mediatriz. 


{\proposicao\label{abparalelo} Dados dois pontos $A=(x_a,y_a)$ e $B=(x_b,y_b)$, seja $m$ a inclinação do segmento $\overline{AB}$. Se $m=0$ então a t\'axi-mediatriz entre $A$ e $B$ ser\'a a reta $ x=\displaystyle\frac{x_a+x_b}{2}$. Se o segmento $\overline{AB}$ é vertical então $m$ é indefinida e a t\'axi-mediatriz ser\'a a reta $y=\displaystyle \frac{y_a+y_b}{2}$.}\\


Note que neste caso a táxi-mediatriz coincide com a mediatriz na métrica euclidiana. A Figura \ref{paraleloxy} ilustra este fato considerando dois pontos $A$ e $B$ e as distâncias entre os pontos $P_1$ e $P_2$ sobre a táxi-mediatriz e os pontos $A$ e $B$.

 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{paralelox.eps} \\
\caption{T\'axi-mediatriz quando $m=0$.}
\label{paralelox}
\end{figure}


 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{paraleloy.eps}\\
\caption{T\'axi-mediatriz quando $m$ \'e indefinido.}
\label{paraleloy}
\end{figure}


O seguinte resultado considera os casos em que $|m|\neq 1$  e $m\neq 0$. As Figuras \ref{taxivoronoi2casos1} e \ref{taxivoronoi2casos2} representam as típicas táxi-mediatrizes para $m>1$ e $0<m<1$. Para um desenvolvimento mais construtivo deste resultado veja \cite{scaburi:2016}.



\begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{taximediatrizinclinado3.eps}\\
\caption{T\'axi-mediatriz para $0<m<1$.}
\label{taxivoronoi2casos1}
\end{figure}


{\proposicao Dados dois pontos $A=(x_a,y_a)$ e $B=(x_b,y_b)$, seja $m$ a inclinação do segmento $\overline{AB}$.\\

\begin{itemize}

\item Se $0<m<1$  então a táxi-mediatriz entre $A$ e $B$ é formada pelo segmento de reta entre os pontos $\left(x_a+\frac{(x_b-x_a)(1-m)}{2},y_b \right)$ e $\left(x_a-\frac{(x_b-x_a)(1-m)}{2},y_a \right)$, a parte da reta $x=x_a+\frac{(x_b-x_a)(1-m)}{2}$ correspondente a $y\geq y_b$ e a parte da reta $x=x_b-\frac{(x_b-x_a)(1-m)}{2}$ correspondente a $y\leq y_a$.

\item Se $1<m$ então a táxi-mediatriz entre $A$ e $B$ é formada pelo segmento de reta entre os pontos $\left(x_a,y_b-\frac{(x_b-x_a)(m-1)}{2}\right)$ e $\left(x_b,y_a+\frac{(x_b-x_a)(m-1)}{2} \right)$, a parte da reta $y=y_a+\frac{(x_b-x_a)(m-1)}{2}$ correspondente a $x\geq x_b$ e a parte da reta $y=y_b-\frac{(x_b-x_a)(m-1)}{2}$ correspondente a $x\leq x_a$.


\item Se $-1<m<0$ então  a táxi-mediatriz entre $A$ e $B$ é formada pelo segmento de reta entre os pontos $\left(x_a+\frac{(x_b-x_a)(1+m)}{2},y_b \right)$ e $\left(x_a-\frac{(x_b-x_a)(1+m)}{2},y_a \right)$, a parte da reta $x=x_a+\frac{(x_b-x_a)(1+m)}{2}$ correspondente a $y\leq y_b$ e a parte da reta $x=x_b-\frac{(x_b-x_a)(1+m)}{2}$ correspondente a $y\geq y_a$.

\item Se $m<-1$ então a táxi-mediatriz entre $A$ e $B$ é formada pelo segmento de reta entre os pontos $\left(x_a,y_b+\frac{(x_b-x_a)(-m-1)}{2}\right)$ e $\left(x_b,y_a-\frac{(x_b-x_a)(-m-1)}{2}\right)$, a parte da reta $y=y_a-\frac{(x_b-x_a)(-m-1)}{2}$ correspondente a $x\geq x_b$ e a parte da reta $y=y_b+\frac{(x_b-x_a)(-m-1)}{2}$ correspondente a $x\leq x_a$.
\end{itemize}
}


\begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{taximediatrizinclinado1.eps}\\
\caption{T\'axi-mediatriz para  $m>1$.}
\label{taxivoronoi2casos2}
\end{figure} 



A proposição seguinte considera o caso em que $|m|=1$. Nesta situação a t\'axi-mediatriz n\~ao \'e formada apenas por retas ou segmentos de reta, sendo formada por um segmento de reta unido a dois \textit{quadrantes do plano} como é ilustrado nas Figuras \ref{mediatrizm1} e  \ref{mediatrizm-1}


{\proposicao A t\'axi-mediatriz  de um segmento com inclina\c{c}\~ao $|m|=1$  \'e formada pela uni\~ao de um segmento de reta e dois quadrantes conforme os dois casos a seguir:
\begin{itemize}
\item  Se $m=1$ a t\'axi-mediatriz \'e formada pelos quadrantes ($x\leq x_a$, $y\geq y_b$) e ($x\geq x_b$, $y\leq y_a$), e pelo segmento da reta $y=\frac{x_a+y_a+x_b+y_b}{2}-x$ para $x_a<x<x_b$.
\item  Se $m=-1$ a t\'axi-mediatriz \'e formada pelos quadrantes ($x\leq x_a$, $y\leq y_b$) e ($x\geq x_b$, $y\geq y_a$), e pelo segmento da reta $y=\frac{-x_a+y_a-x_b+y_b}{2}+x$ para $x_a<x<x_b$.
\end{itemize}
}

Com os conceitos anteriores sobre a táxi-mediatriz, é possível construir uma ilustração mais completa em GeoGebra, como por exemplo a disponível em https://ggbm.at/aAwc9pdJ \footnote{Autoria de Marco Antônio Manneta}.

 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{mediatrizm1.eps}
\caption{T\'axi-mediatriz para $m=1$.}
\label{mediatrizm1}
\end{figure}

 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{mediatrizm-1.eps}
\caption{T\'axi-mediatriz para $m=-1$.}
\label{mediatrizm-1}
\end{figure}

\newpage

\section{Representação do diagrama de Voronoi na Métrica do Táxi}

Nesta seção será apresentado um procedimento para obter uma representação do diagrama de Voronoi na métrica do táxi.  A ideia é a seguinte: Inicialmente considere para cada ponto do conjunto $P=\{p_1,p_2,\cdots,p_n\}$ uma táxi-circunferência de centro em $p_i$ e raio $r$. 

 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{figura18.eps}
\caption{Táxi-Circunferências de centro em $p_i$ e raio $r$.}
\label{r0infty}
\end{figure}

Consideremos também que o raio $r$ varia de forma contínua sobre o intervalo $[0,\infty)$. Quando $r=0$, o único ponto sobre a táxi-circunferência é o próprio ponto $p_i$, mas quando $r$ vai aumentando, qualquer ponto $p$ do plano estará em algum momento sobre a circunferência correspondente ao ponto $p_i$. 

A primeira vez que $p$ esteja sobre a táxi-circunferência de centro em $p_i$, para algum $i$, isto seria equivalente a dizer que $p$ está mais próximo ou pelo menos a mesma distância de $p_i$ do que de qualquer outro ponto $p_j$, ou seja, $p$ pertence à célula de Voronoi $V(p_i)$ se é atingido primeiro pela circunferência correspondente a $p_i$. Por outro lado, se fosse possível que $r$ toma-se como valor inicial $\infty$ e fosse decrescendo até 0, então todos os pontos estariam em algum momento sobre cada táxi-circunferências, mas só a última vez que um ponto $p$ fosse \textit{tocado} por uma táxi-circunferência com centro em algum $p_i$, isto significaria que $p$ seria um elemento da célula associada ao ponto $p_i$.

É possível emular esta ideia em GeoGebra com uso de cores dinâmicas e utilizando a opção de rastro para as táxi-circunferências. É claro que não é possível inicializar $r$ no valor $\infty$ mas para uma escolha inicial suficientemente grande, é possível obter uma representação aproximada do diagrama de Voronoi. 


\begin{figure}[!ht]
\centering
\includegraphics[height=6cm]{figura19.eps}
\caption{Representação do Diagrama de Voronoi na métrica do Táxi}
\label{r0R1}
\end{figure}


No exemplo ilustrado na Figura \ref{r0R1}  foi considerado $r$ com valor inicial 13. A Figura \ref{r0R2} mostra a situação quando  quando $r=4$, e é possível notar como o rastro deixado pelas táxi-circunferências vá colorindo diversos pontos do plano e as células correspondentes a cada ponto começam a ser esboçadas. Um mesmo ponto pode ter diferentes cores em diferentes momentos, mas a cor deixada pela última circunferência que o atinge, indicará a célula de Voronoi a qual pertence.


 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{figura20.eps}
\caption{Representação do Diagrama de Voronoi na métrica do Táxi.}
\label{r0R2}
\end{figure}

Na Figura \ref{r0R3} aparece o resultado final deste processo: uma representação aproximada do diagrama de Voronoi na métrica do táxi para $P=\{p_1, p_2, p_3, p_4, p_5\}$. 

 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{figura21.eps}
\caption{Representação do Diagrama de Voronoi na métrica do Táxi.}
 \label{r0R3}
\end{figure}

A partir da Figura \ref{r0R3}, é possível ver que no caso da métrica do táxi, as células não são necessariamente regiões convexas. A Figura \ref{r0R3} parece sugerir também que as células ilimitadas correspondem a pontos $p_i$ na fronteira do fecho convexo de $P$, mas como é ilustrado na Figura \ref{r0R4}, esto não é necessariamente verdade. O procedimento descrito anteriormente pode ser explorado na animação disponível em https://ggbm.at/US6vBbV4. 


 \begin{figure}[!ht]
 \centering
\includegraphics[height=6cm]{figura22.eps}
\caption{Célulás ilimitadas não correspondem a pontos na fronteira do fecho convexo.}
 \label{r0R4}
\end{figure}


%\section{Sugestão de Atividades em Sala de Aula}
%
%Algumas ideias relacionadas ao diagrama de Voronoi e à métrica do táxi, podem ser exploradas em sala de aula como uma atividade complementar relacionada a diversos conteúdos do Ensino Médio. Isto pode ser feito com ou sem ajuda de ambientes de geometria dinâmica. A seguir são descritas algumas atividades sugeridas em \cite{scaburi:2016}.
%
%\begin{itemize}
%\item Dados três pontos no plano, como determinar as equa\c{c}\~oes das semirretas que correspondem ao diagrama de Voronoi dos tr\^es pontos? Para resolver este problema será preciso considerar a equa\c{c}\~ao da reta a partir de  dois pontos, conceitos de ortogonalidade, ponto médio entre pontos e a equação da reta usando inclinação e um ponto. Também é possível resolver este problema usando a forma paramétrica da equação da reta. O objetivo é obter não só as equações das semirretas mas também a descrição adequada de qual parte de cada semirreta faz parte do diagrama de Voronoi.
%
%\item Um casal mora em uma cidade planejada cuja malha de ruas é perfeitamente quadriculada e com quadras da mesma dimensão. Alice trabalha no ponto $A$ e Bruno trabalha no ponto $B$. Em qual regi\~ao devem procurar um apartamento para que a soma das dist\^ancias ao trabalho de Alice e de Bruno seja a menor poss\'ivel? Para resolver este problema é preciso considerar, além dos conceitos de coordenadas cartesianas, os conceitos de táxi-mediatriz e retângulo básico (uma noção correspondente a ideia de segmento entre pontos). O objetivo é determinar a região adequada e mostrar como esta região pode variar dependendo da inclinação entre os pontos $A$ e $B$.
%\end{itemize}
%
%Outras possíveis atividades podem ser desenvolvidas ao redor de questões hipotéticas explorando ideias como as seguintes: 
%
%\begin{itemize}
%\item Se numa cidade há 10 pontos de distribuição de vacinas, a qual ponto deveria se dirigir alguém localizado no ponto $A$?
%\item Dados dos pontos $A$ e $B$, se dois corredores tem a mesma velocidade, quem chegará mais rápido ao ponto $C$?
%\end{itemize}
%
%Outras ideias para o desenvolvimento de atividades em sala de aula podem ser encontradas em \cite{okabe2009spatial, krause2012taxicab, rpm50a}.


\section{Comentários Finais}

Ao longo do trabalho foi descrita a utilização do GeoGebra, tanto para ilustrar resultados teóricos relacionados ao diagrama de Voronoi na métrica euclidiana, como para a exploração dos conceitos de táxi-circunferência e táxi-mediatriz. Estes resultados e conceitos estão baseados em ideias simples, mas nem sempre é imediata a sua compreensão. O uso do GeoGebra  permite  aprimorar a compreensão destes conceitos. Foi ilustrado também, que uma implementação direta no GeoGebra da equação da táxi-mediatriz, poderia levar a confusões sem a adequada fundamentação teórica. Foi descrito também como GeoGebra pode ser usado para produzir uma representação do diagrama de Voronoi na métrica do táxi.  É importante destacar que este procedimento de representação pode ser estendido a outras métricas, se há uma construção adequada da circunferência correspondente. Finalmente, queremos destacar que as ligações entre as ideias aqui discutidas e alguns conceitos considerados no ensino médio, permitem ao professor de Matem\'atica estabelecer situações-problemas interessantes, com aplica\c{c}\~oes diretas de conceitos geométricos e que quando desenvolvidas com ajuda de ferramentas computacionais como GeoGebra, podem estimular o processo de aprendizado.


%\section{Conclusões}
%Esperamos que este arquivo possa ser útil na elaboração de seu artigo, qualquer dúvida
%envie um e-mail (recen.unicentro@gmail.com) para mais esclarecimentos. Antes da publicação, após
%as correções, o artigo será enviado aos autores para confirmação da formatação final. Deve
%ser conferido e devolvido imediatamente.

\begin{thebibliography}{999}
%A bibliografia deve ser feita utilizando \bibitem {x} AUTOR1; AUTOR2; Título, volume, número , data
%Onde x é um código que deve-se criar para cada referencia
%As citações devem ser inseridas aqui na ordem em que aparecem no texto 

\bibitem{okabe2009spatial}
OKABE, A.; BOOTS, B.; SUGIHARA, K.; CHIU, S.N. \textit{Spatial Tessellations: Concepts and Applications of Voronoi Diagrams}. Wiley Series in Probability and Statistics, 2009.

\bibitem{de2008computational}
de BERG, M. \textit{Computational Geometry: Algorithms and Applications}. Springer, 2008.

\bibitem{notasIMPA}
  de FIGUEIREDO, L.H.; CARVALHO, P.C. P. \textit{Notas de Geometria Computacional}. IMPA, 2009.

\bibitem{voronoi}
LIEBLING, T. M.; POURNIN, L. \textit{Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twins}. Documenta Mathematica, Extra Volume ISMP, p.~419-431, 2012. 


\bibitem{johnson2008mapa}
JOHNSON, S. \textit{O mapa fantasma: Como a luta de dois homens contra a cólera mudou o destino de nossas metrópoles}. Zahar, 2008.

\bibitem{scaburi:2016}
SCABURI dos SANTOS, P. \textit{Diagrama de Voronoi: Uma exploração nas distâncias Euclidiana e do táxi.} Dissertação de Mestrado,  Mestrado Profissional em Matemática em Rede Nacional PROFMAT, 2016.

\bibitem{krause2012taxicab}
KRAUSE, E.F. \textit{Taxicab Geometry: An Adventure in Non-Euclidean Geometry}. Dover Publications, 1986.

\bibitem{rpm50a}
WANDERLEY A.J.M.; CARNEIRO J.P.Q.; WAGNER E. \textit{Como melhorar a vida de um casal usando geometria não-euclidiana}. Revista do Professor de Matem\'atica, v.~50, p.~23-30, 2001.
  

\end{thebibliography}

\end{document}