\input ReportFormat.tex \input Portuguese.tex

\begfile{USPR83.tex of December 29, 1983 6:56 pm --- Stolfi}

\title{\lbf JORGE STOLFI --- Relat\'orio de Atividades\lb
  \smc outubro de 1982 a setembro de 1983}

% Reference macros

\def\Fourier{1}
\def\Opt{2}
\def\Edm{3}
\def\Furst{4}
\def\GSBOP{5}
\def\GSNotes{6}
\def\GSVor{GSVor}
\def\GSNE{GSNE}
\def\GSK{GSK}
\def\EGSLoc{EGSLoc}
\def\ShHo{ShHo}
\def\JALG{JALG}
\def\Jap{7}
\def\CLang{8}
\def\Kirk{9}
\def\LeeP{10}
\def\VLSI{11}

\section{1. Sum\'ario}

No trimestre de outono (outubro a dezembro) de 1892 continuei estudando a estrutura de dados que desenvolvi no ver\ao\ para a 
representa\cao\ de diagramas planares, e consegui generaliz\'a-la para diagramas embebidos em variedades bi-dimensionais 
arbitr\'arias. Estudei tamb\'em a correspond\>encia entre o diagrama de Voronoi the $n$ pontos no plano e o casco convexo de $n$ 
pontos no espa\co. Juntamente com o Prof. Leo Guibas, escrevi um artigo a respeito destes assuntos [\GSVor], que apresentamos no 
$15\deg$ {\it Symposium on Theory of Computing (STOC)} da ACM, em abril de 1983.

Neste per\ii odo tambem colaborei com o Prof. Guibas no desenvolvimento de um algoritmo para construir a \'arvore de comprimento 
m\ii nimo para um conjunto dado de v\'ertices no plano, na m\'etrica $L
1$, em tempo $O(n\log n)$ e espaco $O(n)$. Nosso artigo a 
respeito [\GSNE] foi recentemente publicado. Escrevemos tambem uma nota [\GSK] a respeito da solu\cao\ eficiente de problemas de 
programa\cao\ linear em $\reals^3$ quando as restri\coes\ permanecem fixas e a fun\cao\ objetivo varia.

No inverno (janeiro a mar\,co) de 1983, trabalhei como monitor do Prof. Guibas, que ministrou novamente o curso de Geometria 
Computacional por \>ele criado no ano anterior. Como parte desta atividade, acrescentei tr\>es novos cap\ii tulos \`as notas de 
aula que preparei no ano anterior, e preparei uma bibliografia de artigos em Geometria Computacional (em anexo). Neste per\ii odo 
assisti tambem ao semin\'ario CS460 {\it Criptography???}, ministrado pelo Prof. Andrew C. Yao.   

Na primavera (abril a junho) de 1983 trabalhei com o Prof. Guibas e o Dr. Lyle Ramshaw no desenvolvimento de uma nova teoria de de 
curvas no plano e na esfera, e suas aplica\coes\ em Geometria Computacional. Nosso trabalho a respeito foi aceito para 
apresenta\cao\ no  {\it $24^{th}$ IEEE Symposium on Foundations of Computer Science (FOCS)}, a ser realizado em novembro de 1983.

No ver\ao\ (julho a setembro) de 1983 estudei tambem o problema da localiza\cao\ eficiente de um ponto numa subdivi\sao\ poligonal 
do plano. Em colabora\cao\ com o Prof. Guibas e com o Dr. Herbert Edelsbrunner, consegui desenvolver um algoritmo [\EGSLoc] que \'e 
te\'oricamente \'otimo e pr\'aticamente eficiente.

Palestra do AFLB

Em ??? escolhi formalmente o t\'opico para minha disserta\cao\ de Doutoramento ({\it Prmitives for Computational Geometry in the 
Plane}) Os seguintes professores do Departamento concordaram em fazer parte de minha banca examinadora: Donald E. Knuth (orientador 
oficial), Ernst Mayr, Andrew C. Yao e Leo J. Guibas (orientador {\it de facto}).     

TGR? FOO

Incu\ii ndo os cursos aqui relacionados, completei at\'e agora um total de ?? cr\'editos, distribu\ii dos pelos seguintes 
departamentos: Computer Science, ??; Mathematics, ?; Electrical Engineering, ??; Asian Languages, ??. Estes cr\'editos mais que 
perfazeram o total exigido pelo Departamento. Tendo completado tambem ?? trimestres de anuidade integral, passei \`a categoria de 
``terminal graduate student'' (TGR), o que reduziu a anuidade a aproximadamente $500 por trimestre.  

Segue-se uma descri\cao\ mais detalhada das atividades acima, e meus planos para o pr\'oximo per\ii odo. 

\vfill\eject

\section{2. Diagramas bi-dimensionais}

Um {\it diagrama bi-dimensional} \'e essencialmente um grafo n\ao\ dirigido embebido numa variedade bi-dimensional compacta, isto 
\'e, numa superf\ii cie limitada e sem borda. As superf\ii cies da esfera e do toro s\ao\ dois exemplos de tais variedades. Outro 
exemplo \'e o plano projetivo, obtido da esfera pela identifica\cao\ de pontos diametralmente opostos. Grafos emebebidos no plano 
podem ser considerados diagramas bi-dimensionais, uma vez que a adi\cao\ de um ponto ou de uma reta fict\ii cia no infinito 
transforma o plano euclidiano respectivamente na esfera ou no plano projetivo. Diagramas bi-dimensionais, especialmente diagramas 
planares, desepenham um papel central em muitos problemas de geometria computacional e an\'alise combinatoria. Exemplos de tais 
diagramas s\ao: superf\ii cies de poliedros, diagramas de Voronoi, triangula\coes\ de pol\ii gonos, e assim por diante.

Como parte de minhas pesquisas sobe os diagramas de Voronoi, desenvolvi no ver\ao\ de 1982 uma nova estrutura de dados para 
representar diagramas bi-dimensionais, que batizamos de estrutura {\it quad-edge}. Esta \'e uma exten\sao\ da estrutura {\it 
winged-edge} descrita por \bug [\WEdg].  Nesta \'ultima, cada aresta $a$ do diagrama $D$ \'e representada por um registro com oito 
apontadores, que indicam os dois vertices e as duas faces incidentes na aresta $a$, e as quatro arestas imediatamente adjacentes 
\'a mesma.

A estrutura {\it quad-edge} tambem usa oito apontadores para cada aresta $a$ do diagrama, com aproximadamente o mesmo significado. 
Esses apontadores s\ao\ por\'em distribu\ii dos em quatro registros semelhantes, em posi\coes\ cont\ii guas da mem\'oria. Dois 
desses registros correspondem \`as duas poss\ii veis orienta\coes\ da aresta $a$, e os outros dois \'as duas orienta\coes\ da 
aresta $a\star$ correspondente a $a$ no diagrama dual $D\star$. Cada registro portanto corresponde a uma aresta {\it dirigida} $\b 
a$ de $D$ ou $D\star$, e cont\'em dois apontadores: um para o v\'ertice de origem de $\b a$, e um para a aresta com mesma origem e 
imediatamente seguinte a $\b a$ (em sentido anti-hor\'ario).

A defini\cao\ de ``sentido anti-hor\'ario'' \'e relativa a uma orienta\cao\ espec\ii fica da superf\ii cie na qual o diagrama 
est\'a embebido, numa vizinhan\,ca discoidal da aresta em quest\ao. Essa ``orienta\cao\ de refer\>encia'' pode ser escolhida 
arbitr\'aria e independentemente para cada aresta (esta flexibilidade \'e obviamente essencial quando a superf\ii cie n\ao\ \'e 
orient\'avel). Todo apontador para um registro de aresta inclui um bit adicional, que especifica se tal aresta deve ser tomada com 
sua orienta\cao\ normal ou com a oposta; neste \'ultimo caso, os significados de ``hor\'ario'' e ``anti-hor\'ario'' s\ao\ 
invertidos para essa aresta.

A principal vantagem da estrutura {\it quad-edge} \'e que ela representa simult\>aneamente um diagrama $D$, seu dual $D\star$, e as 
imagens especulares de $D$ e $D\star$, usando apenas alguns bits  a mais por aresta do que o necess\'ario para represntar $D$. Mais 
ainda, esses quatro diagramas podem ser obtidas em tempo $O(1)$ (bastando para tal modificar dois ou tres bits de um apontador para 
qualquer aresta em $D$), e tem o mesmo formato que $D$. Para ilustrar a flexibilidade resultante deste fato, considere o problema 
de construir um diagrama formado pela jun\cao\ de um cubo a um octaedro. A estrutura {it quad-edge} permite-nos construir dois 
cubos (atrav\'es de duas chamadas da mesma sub-rotina), e conectar um ao dual do outro. Outras representa\coes\ correntes 
(incluindo a estrutura {\it winged-edge}) exigiriam a constru\cao\ do cubo e do octaedro por duas sub-rotinas distintas.

Uma conseq\"uencia desta uniformidade \'e uma redu\cao\ substancial no n\'umero de sub-rotinas necess'arias para manipular tais 
diagramas. Na verdade, descobri que duas oper\coes\ fundamentais, ambas extremamente simples e eficientes, s\ao\ suficientes para 
construir qualquer diagrama, e para efetuar modifica\coes\ arbitr\'arias no mesmo. Uma destas opera\coes\ cria uma subdivis\ao\ 
trivial da esfera, consistindo de uma aresta, um v\'ertice e duas faces. A outra opera\cao\ toma duas arestas, e, dependendo da 
situa\cao relativa das mesmas, junta e/ou separa os v\'ertices e as faces nelas incidentes.

A descri\cao\ detalhada da estrutura {\it quad-edge} pode ser encontrada no artigo que o Prof. Leo Guibas e eu apresentamos no {\it 
15$\null^{th}$ ACM Symposium on Theory of Computing}, Boston, em abril de 1983 [\GSVor]. Nesse artigo provei tambem que a estrutura 
{\it quad-edge} \'e ``categ\'orica'', isto \'e, toda estrutura bem-formada corresponde a um \'unico diagrama bi-dimensional, e 
vice-versa. Provei tambem a sufici\>encia e corre\cao\ das duas opera\coes\ fundamentais mencinadas acima. Exemplos de aplica\coes\ 
da estrutura {\it quad-edge} s\ao\ os algoritmos para a constru\cao\ de diagramas de Voronoi [\GSVor] e num algoritmo eficiente 
para a localiza\cao\ um ponto num diagarama planar que estamos desenvolvendo (vide se\cao\ 4 deste relat\'orio e refer\>encia 
\EGSLoc).
       
\section{3. \'Arvore m\ii nima na m\'etrica $L
1$}

Uma {\it \'arvore} \'e um grafo na\ao\ dirigido, ac\ii clico e conexo. Muitos problemas de inter\>esse pr\'atico podem ser 
reduzidos \`a determina\cao\ de uma \'arvore cujos v\'ertices s\ao\ $n$ pontos dados no plano, tal que o comprimento total da 
\'arvore (a soma dos comprimentos de suas arestas) \'e a menor poss\ii vel. O comprimento de uma aresta geeralmente \'e 
interpretado sendo a dist\>ancia euclideana entre seus v\'ertices; em algumas aplica\coes, entretanto, \'e necess\'ario usar outras 
medidas, notadamente as dist\>ancias $L
1$ ou $L
\infty$. estas s\ao\ definidas respectivamente como sendo a soma ou o m\'aximo das 
diferen\,cas, em valor absoluto, entre as coordenadas dos dois pontos.     

Este \'e um caso particular do problema da {\it \'arvore espalhada de m\ii nimo custo}: dado um grafo conexo $G$, e uma fun\cao\ 
que atribui a cada aresta de $G$ um ``custo'' arbitr\'ario, encontrar o sub-grafo ac\ii clico conexo de $G$ tal que a soma dos 
custos de suas arestas \'e minima. Sabe-se que tal \'arvore pode ser determinada em tempo $O(m\log m)$, onde $m$ \'e o n\umero de 
arestas de $G$. Um algoritmo com tais caracter\ii sticas \'e o de Kruskal, na vers\ao\ de D. Cheriton e R. E. Tarjan [\CheTar].

Portanto, uma maneira de determinar a \'arvore de comprimento m\ii nimo para $n$ pontos no plano \'e construir o grafo completo $K$ 
com tais pontos como v\'ertices, e definir o custo de cada aresta omo sendo seu comprimento. Esta solu\cao\ n\ao\ \'e muito 
interessante na pr\'atica: uma vez que $K$ tem $\Omega(n^2)$ arestas, o tempo de processamento pode chegar a $\Omega(n^2\log n)$.

Apesar disso, muitos algoritmos \'otimos para o problema da \'arvore de comprimento m\ii nimo s\ao baseados numa modifica\cao\ 
deste m\'etodo geral. A modifica\cao\ consiste em considerar, em vez do grafo completo $K$, um grafo $G$ que \'e ao mesmo tempo 
denso o bastante para conter com certeza a \'arvore de comprimento m\ii nimo, e esparso o bastante para ser eficientemente 
processado pelo algoritmo de Kruskal. Em particular, se o grafo $G$ tem $O(n)$ arestas e pode ser constru\ii do em tempo $O(n\log 
n)$, este me\'etodo produz um algoritmo \'otimo para o problema.

Um exemplo de um grafo com essas propriedades \'e o {\it diagrama de Delaunay} dos pontos dados, o dual do diagrama de Voronoi. Um 
algoritmo para a constru\cao\ de tal diagrama, para qualquer m\'etrica $L
p$, \'e o descrito por D. T. Lee [\LeeLp]. Outro exemplo 
\'e o do grafo proposto por A. C. Yao [\YaoMST], no qual cada v\'ertice $v$ \'e ligado por uma aresta ao v\ertice mais pr\'oximo de 
$v$, em cada um dos octantes do plano determinados por $v$. Obviamente, o diagrama de Yao tem menos de $8n$ arestas, e pode-se 
provar que ele cont\'em a \'arvore de comprimento m\ii nimo. Comparado com o diagrama de Dealunay, o de Yao tem a importante 
vantagem de ser aplic\'avel (com as devidas generaliza\coes) na determina\cao de \'arvores m\ii nimas em espa\,cos de dimens\ao\ 
maior que 2. No caso do plano, entretanto, o algoritmo proposto por Yao para sua constru\cao\ exige tempo $O(n^{15/8}(\log 
n)^{7/8})$, contra os $O(n\log n)$ suficientes para a constru\cao\ do diagrama de Delaunay.   

No outono de 1982, o Prof. Guibas e eu conseguimos desenvolver um algoritmo para a constru\cao\ do grafo de Yao no plano, na 
m\'etrica $L
1$ (ou $L
\infty$), em tempo $O(n\log n)$. Com este algoritmo, a constru\cao da \'arvore m\ii nima pode ser efetuada 
atrav\'es do grafo de yao ou de Delaunay, com a mesma efici\>encia asint\'otica. Na verdade, a constru\cao\ do diagrama de Yao pelo 
nosso algoritmo \'e bem mais simples e r\'apida que a do o diagrama de Delaunay, o que pode tornar o primeiro prefer\ii vel na 
pr\'atica. O algoritmo foi recentemente publicado na revista {\it Information Processing Letters} [\GSNE].
 
\section{4. Localiza\cao\ de um ponto no plano}

O {\it problema da localiza\cao\ de um ponto no plano} \'e seguinte: dada uma parti\cao\ do plano em $n$ regi\oes\ de determinado 
tipo (por exemplo, pol\'\i gonos), e dado um ponto arbitr\'ario $p$, determinar a regi\ao\ que contem $p$. Este problema \'e um dos 
mais importantes na \'area de Geometria Computacional, uma vez que o mesmo possui um grande n\'umero de aplica\coes\ e \'e 
frequentemente a etapa das mesmas que consome a maior parte do tempo de processamento. 

Quando o problema \'e localizar um {\it \'unico} ponto, a solu\cao\ trivial (que consiste em testar o ponto contra todas as 
regi\oes) \'e \'otima, e exige tempo $O(n)$. Muitas aplica\coes, entretanto, exigem a localiza\cao\ de um grande n\'umero de pontos 
contra uma {\it mesma} sub-divisao $S$. Em tais casos, \'e prefer\ii vel re-codificar primeiro $S$ de forma a simplificar a 
localiza\cao\ de cada ponto. Um algoritmo \'otimo para esta vers\ao\ do problema \'e o devido a D. Kirkpatrick [\Kirk]. Este 
algoritmo consome $O(n)$ tempo e espa\,co no pr\'e-processamento da subdivis\ao, ap\'os o que \>ele consegue localizar cada ponto 
em tempo $O(\log n)$.  Infelizmente, a complexidade do algoritmo de Kirkpatrick impede seu uso generalizado na pr\'atica.  

Em conex\ao\ com meu trabalho sobre diagramas de Voronoi, dispendi algum tempo no outono de 1982 estudando este problema. N\ao\ 
tendo conseguido melhorar a efici\>encia do algoritmo de Kirpatrick, voltei minha aten\cao\ para um algoritmo devido a D. T. Lee e 
F. Preparata [\LeeP]. Este algoritmo \'e te\'oricamente inferior ao de Kirkpatrick (pois exige $O(n\log n)$ tempo para o 
pr\'e-processamento, e $O(\log n)^2$ para localizar cada ponto), mas \'e bem mais f\'acil de implementar e mais econ\>omico em 
termos de espa\,co, e \'e razoavelmente r\'apido na pr\'atica. Outra vantagem do m\'etodo de Lee e Preparata \'e que o mesmo pode 
ser usado inclusive em sub-divis\oes\ com arestas n\ao-retil\ii neas.

O algoritmo de Lee e Preparata aplica-se a sub-divis\oes\ {\it monot\>onicas}, caracterizadas pela propriedade que toda reta 
vertical intercepta a fronteira de qualquer regi\ao\ em no m\'aximo dois pontos. Ao estudar tais sub-divis\oes, observei que, para 
todo inteiro positivo $k$ menor que o n\'umero de regi\oes\ $n$, existe uma curva $s
k$ que intercepta cada reta vertial num 
\'unico ponto, e que separa $k$ regioes das restantes $n-k$ [\JALG]. Observei tamb\'em que  que esta linha pode ser determinada em 
tempo $O(n)$. Este resultado me permitiu simplificar bastante a etapa de pr\'e-processamento do algoritmo de Lee e Preparata, e 
reduzir o tempo consumido pela mesma para $O(n)$.

Ao submeter para publica\cao\ um artigo relatando estes melhoramentos, fui informado que o Dr. Herbert Edelsbrunner (da 
Universidade T\'ecnica de Graz, \'Austria) tinha conseguido independenemente reduzir o tempo de localiza\cao\ do algoritmo de Lee e 
Preparata para $O(log n)$ por ponto. Combinando nossos resultados, otivemos portanto um algoritmo que \'e ao mesmo tempo \'otimo em 
teoria, e simples e eficiente na pr\'atica. Estamos no momento preparando um artigo conjunto para publica\cao\ no {\it SIAM Journal 
on Computing}. 

\section{5. Problemas lineares m\'ultiplos}

No outono de 1982 o Prof. Guibas, Ken Clarkson (estudante na Universidade de Stanford) e eu constatamos que um algoritmo eficiente 
para a localiza\cao de um ponto numa sub-divis\ao\  do plano, como por exemplo o algoritmo de Kirkpatrick [\Kirk], permite resolver 
de maneira eficiente uma cole\cao\ de $m$ problemas de programa\cao\ linear em tres vari\'aveis que compartilham as mesmas 
restri\coes e que diferem apenas na fun\cao\ objetivo.   

As restri\coes desses problemas definem uma ``regi\ao\ fact\ii vel'', consistindo de todos os pontos de $\reals^3$ que satisfazem a 
todas as restri\coes. A regi\ao\ fact\ii vel determinada por $n$ inequa\coes lineares, quando n\ao\ vazia, \'e um poliedro $P$ com 
$O(n)$ faces. Cada problema da cole\cao\ consiste em determinar o ponto deste poliedro que maximiza uma determinada fun\cao\ 
objetivo $f$, linear nas coordenadas do ponto. Isto equivale a determinar o plano perpendicular ao gradiente de $f$ e tangente ao 
poliedro $P$, e o ponto de tang\>encia entre os dois.

{\bf STOPPED HERE December 29, 1983 6:56 pm}   

\section{6. Teoria cin\'etica de curvas}

\section{7. Outras pesquisas.}

{\bf JUNK} Uma das aplica\coes\ mais importantes do problema da localiza\cao\ \'e o {\it problema do ponto mais pr\'oximo}: dados 
$n$ pontos $p
1, p
2, ... p
n$ no plano, e um ponto arbitr\'ario $q$, determinar qual dos $p
i$ est\'a mais pr\'oximo de $q$. Se a 
cada um dos $p
i$ associarmos uma regi\ao $P
i$ do plano, tal que $q$ pertence a $P
i$ se e somente se $q$ est\'a mais pr\'oximo de 
$p
i$ do que de qualquer outro $p
j$, obteremos uma decomposi\cao\ do plano em $n$ pol\ii gonos convexos, conhecida como o {\it 
diagrama de Voronoi} dos pontos $p
i$.

Obviamente, a determina\cao\ do ponto $p
i$ mais pr\'oximo a $q$ reduz-se ao da localiza\cao\ de $q$ no diagrama de Voronoi. Certas 
propriedades deste \'ultimo (que n\ao\ s\ao\ compartilhadas por ourtras decomposi\coes\ convexas do plano) prometem conduzir a 
vers\oes\ mais simples dos algoritmos de localiza\cao\ acima mencionados.

\vfill\eject

\section{8. Cursos}

\vfill\eject

\section{9. Planos para o pr\'oximo per\ii odo}

{\bf JUNK}

\date{28 de Dezembro de 1983\blam}

\signed{Jorge Stolfi}

\vfill\eject

\section{Bibliografia}

\def\refauth#1{\unskip {\smc #1}} % Author (s)
\def\reftit#1{\unskip\unskip, {\it #1}} % Title
\def\refpub#1{ {\rm #1}} % Publication
\parindent 0pt

\ref [\Fourier] {\refauth{R. N. Bracewell}
  \reftit{The Fourier transform and its applications.}
  \refpub{McGraw-Hill, 1978.}}

\ref [\Opt] {\refauth{L. C. W. Dixon}
  \reftit{Nonlinear optimization.}
  \refpub{Crane, Russack & co., N.Y., 1972.}}

\ref [\Edm] {\refauth{J. Edmonds}
  \reftit{A combinatorial representation for polyhedral surfaces.}
  \refpub{Notices of the American Mathematical Society Vol. 7, 1960, p.  646.}}

\ref [\Furst] {\refauth{M. Furst, J. Hopcroft, {\rm e} E. Luks}
  \reftit{Polynomial-time algorithms for permutation groups.}
  \refpub{21$\null^{\hbox{st}}$ Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1980, 36--41.}}

\ref [\GSBOP] {\refauth{L. J. Guibas {\rm e} J. Stolfi}
  \reftit{A language for bitmap manipulation.}
  \refpub{ACM Transactions on Graphics Vol. 1 No. 3, julho/1982, 191--214. (separata em anexo)}}

\ref [\GSNotes] {\refauth{L. J. Guibas {\rm e} J. Stolfi}
  \reftit{Introduction to Computational Geometry.}
  \refpub{(a ser publicado; vers\ao\ preliminar em anexo).}}

\ref [\Jap] {\refauth{E. H. Jorden}
  \reftit{Beginning Japanese.}
  \refpub{Yale University Press, 1963.}}

\ref [\CLang] {\refauth{B. W. Kernighan {\rm e} D. M. Ritchie}
  \reftit{The ``C'' programming language.}
  \refpub{Prentice-Hall, 1978.}}

\ref [\ShHo] {\refauth{M. I. Shamos {\rm e} D. Hoey}
  \reftit{Closest-point problems.}
  \refpub{Proc. 16$\null^{\hbox{th}}$ Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1975, 151--162.}}

\ref [\Kirk] {\refauth{D. Kirkpatrick}
  \reftit{Optimal search in planar subdivisions.}
  \refpub{Technical Report 81-13, Dept. of Computer Science, Univ. of British Columbia, Vancouver.}}

\ref [\LeeP] {\refauth{D. T. Lee {\rm e} F. Preparata}
  \reftit{Location of a point in a planar subdivision and its applications.}
  \refpub{SIAM Journal of Computing Vol. 6, 1977, 594--606.}}

\ref [\VLSI] {\refauth{C. Mead {\rm e} L. Conway}
  \reftit{Introduction to VLSI systems.}
  \refpub{Addison-Wesley, 1980.}}

\par\vfill\eject\end