\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}

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

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).

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].

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}.

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}

{\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

\vfill\eject

{\bf JUNK}

\date{28 de Dezembro de 1983\blam}

\signed{Jorge Stolfi}

\vfill\eject

\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.}}