math.math-mg info.info-dm
Universidade Estadual 
  
D E Campinas 
  
Interseção De 
  
Álgebra Geométrica 
  
Marcelo Santos 
  
Tese Apresentada 
  
Solange Da Fonseca Rutz 
  
Carlile Campos Lavor 
  
Leandro Augusto 
  
Frata Fernandes 
  
Marcelo Carielo 
  
Santos 
  
Solange Da Fonseca 
  
Rutz Carcoorientadores 
  
Cartese 
  
Solange I Rutz 
  
Ii Da Fonseca 
  
Carlile Lavor 
  
Campos 
  
- Iii 
  
Leandro Fernandes 
  
Frata Iv Augusto 
  
Ao Prof 
  
Profa Solange Carlile Lavor 
  
Prof Leandro Rutz 
  
Fernandes 
  
Prof Peter Antonelli 
  
  
  
  
  
  
  
  
  
  
  
  
Keywords: Interseção de esferas, álgebra geométrica, geometria de distâncias, estruturas moleculares Sphere intersection, geometric algebra, distance geometry, molecular structure

O problema de interseção de esferas aparece em diferentes aplicações da geometria de distâncias. Esferas cujos raios são intervalares têm especial interesse quando os dados provém de experimentos físicos, onde há incertezas nas medições. Utilizando a álgebra geométrica conforme, desenvolvemos uma maneira eficiente de realizar a interseção entre esferas e cascas esféricas. Comparamos os resultados obtidos com a abordagem clássica, baseada na álgebra linear, e fizemos experimentos computacionais para validar a abordagem proposta.

Introdução

O problema de interseção de esferas aparece em diversas aplicações [START_REF] Blumenthal | Theory and applications of distance geometry[END_REF][START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF][START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF][START_REF] Davison | Multidimensional scaling[END_REF][START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF]. Alguns modelos matemáticos formulados em tais contextos consideram esferas tanto em espaços tridimensionais (3D) quanto em espaços de dimensão n (nD), sendo que os raios podem ser escalares fixos ou intervalos reais. A posição relativa entre os centros, a dimensão das esferas e do espaço subjacente onde se encontram podem variar de acordo com a formulação do problema. Comumente, o problema da interseção de esferas considerando raios fixos é abordado com ferramentas baseadas na álgebra linear e teoria de matrizes [START_REF] Coope | Reliable computation of the points of intersection of n spheres in R n[END_REF][START_REF] Maioli | Interseção de Esferas no R n e Aplicações[END_REF][START_REF] Datorro | Convex Optimization & Euclidean Distance Geometry[END_REF][START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF]. Quando os raios das esferas são intervalares, surgem as cascas esféricas e o novo problema é a busca de uma maneira adequada para se realizar a interseção entre esferas e cascas esféricas. Destacamos que em tal problema há um interesse especial em métodos que possam ser implementados e validados computacionalmente. Extensões de abordagens convencionais, baseadas em álgebra linear, são levadas a limitações consideráveis quando há esferas intervalares, inviabilizando generalizações principalmente com respeito a aspectos computacionais. Por exemplo, desconhecemos na literatura uma maneira adequada para se realizar a interseção entre p esferas e q cascas esféricas em um espaço nD, onde p, q e n são números inteiros positivos quaisquer fixados. Problemas como esses são de grande interesse do ponto de vista de aplicações, pois considerar esferas com raios intervalares é uma maneira de se incorporar aos modelos dados de entrada com as incertezas presentes em medidas experimentais. Uma discussão sobre o assunto pode ser encontrada em [START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF][START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF].

Ideia Central

Este trabalho investiga o problema de interseção entre esferas e cascas esféricas em espaços nD através da álgebra geométrica conforme (AGC) [START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for computer vision and graphics[END_REF][START_REF] Dorst | Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[END_REF][START_REF] Fernandes | Álgebra Geométrica e Aplicações[END_REF][START_REF] Perwass | Geometric algebra with applications in engineering[END_REF], propondo uma abordagem que se estenda de forma natural ao se acrescentar várias cascas esféricas. Os Capítulos 1 e 2 apresentam as noções básicas para introduzir os problemas vistos nos demais capítulos. Na literatura, o estudo da interseção entre esferas via AGC é comumente apresentado para espaços 3D.

A abordagem usual via AGC para levar em conta as cascas esféricas faz uso dos rotores [START_REF] Alves | Álgebra de Clifford Aplicada ao Cálculo de Estruturas Moleculares[END_REF], enquanto que a abordagem proposta neste trabalho é baseada na parametrização pelo raio. Essa nova escolha para resolver o problema tem facilitado a busca de generalizações de conceitos já conhecidos em 3D. Os resultados obtidos com a abordagem proposta foram comparados com os conhecidos na literatura [START_REF] Coope | Reliable computation of the points of intersection of n spheres in R n[END_REF][START_REF] Maioli | Interseção de Esferas no R n e Aplicações[END_REF][START_REF] Liberti | A branch-and-prune algorithm for the molecular distance geometry problem[END_REF][START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF][START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF]. No Capítulo 3, é sumarizado alguns resultados da abordagem baseada em álgebra linear utilizados para as comparações. O Capítulo 4 mostra os resultados de experimentos onde se compara ambas abordagens: a clássica e a que foi desenvolvida via AGC. Problemas de aplicação foram explorados no contexto do cálculo de estruturas moleculares [START_REF] Liberti | A branch-and-prune algorithm for the molecular distance geometry problem[END_REF][START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF][START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF][START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF][START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF]. A fim de validar a abordagem proposta, realizamos inúmeros experimentos computacionais implementando os resultados teóricos no Mathematica [18] em conjunto com o pacote clifford.m [START_REF] Aragón-Camarasa | Clifford Algebra with Mathematica[END_REF], e também no CLUCalc [START_REF] Perwass | CLUCalc v4.3.2[END_REF]. A abordagem desenvolvida mostrou-se promissora para tratar as incertezas experimentais. Testes computacionais levando em conta as aplicações foram realizados com sucesso, validando diferentes aspectos da tese proposta. Nos Capítulos 5 e 6 há detalhes com respeito a tais questões e sobre as vantagens e potenciais aplicações deste trabalho.

Resultados

Com auxílio da AGC, propomos uma forma eficiente para obter a interseção entre esferas e cascas esféricas em espaços nD. A tese deste trabalho é a seguinte:

As soluções obtidas para o problema de interseção de esferas em espaços nD pela abordagem proposta via AGC são equivalentes às abordagens convencionais, baseadas em álgebra linear. Além disso, possuem vantagens quando o problema leva em conta esferas com raios intervalares. A principal vantagem é permitir o acréscimo de várias cascas esféricas ao problema inicial de forma natural, possibilitando a implementação e validação dos resultados através de experimentos computacionais.

Muitos problemas que apareceram ao longo deste trabalho são de interesse tanto do ponto vista teórico como computacional. Assim, questões relacionadas aos avanços em termos da capacidade em simulações computacionais estão intimamente ligadas a continuidade das pesquisas de caráter teórico. Um exemplo é saber até que ponto um resultado teórico utilizando a AGC, ou a abordagem clássica, poderia ser implementado de forma que, de posse de dados experimentais de entrada, possamos ter tanto um modelo como uma implementação que resolva o problema real da forma mais eficiente possível. Ao longo de todo trabalho, este aspecto da pesquisa se mostra determinante e tem um papel fundamental na construção dos resultados propostos. Enquanto a abordagem clássica se mostra inviável para lidar com problemas envolvendo mais do que uma casca esférica, tanto do ponto de vista teórico quanto computacional, a abordagem desenvolvida neste trabalho levou a resultados positivos em tais situações. Uma maneira de dar continuidade às pesquisas aqui iniciadas é estender os resultados computacionais a uma quantidade arbitrária de cascas esféricas em espaços nD e explorar em detalhes as aplicações envolvendo o cálculo de estruturas 3D moleculares.

Fundamentação teórica

Neste capítulo veremos as definições básicas associadas ao problema de interseção de esferas e algumas de suas aplicações. Apresentaremos de forma resumida certas noções subjacentes ao problema do cálculo de estruturas 3D moleculares. Veremos também aplicações envolvendo espaços nD. (x i j -c i j ) 2 = r 2 , k ≤ n}. Uma k-esfera no R n , para k ≤ n, é uma esfera contida em um subespaço afim de dimensão k.

Algumas definições matemáticas

De forma geral, para obter a interseção de m esferas no R n temos que resolver o seguinte sistema,

||x -a i || = d i , ( 1.1) 
onde a i ∈ R n e d i ∈ R + , denotam o centro e raio da esfera i, para i = 1, . . . , m. De fato, para cada i fixado, a solução da equação (1.1) é uma esfera no R n . Ao longo deste trabalho, denotamos a norma-2 por || • ||.

Em [START_REF] Coope | Reliable computation of the points of intersection of n spheres in R n[END_REF] é apresentado um método para se obter a interseção de n esferas no R n supondo certas restrições com respeito aos centros das esferas. Já em [START_REF] Maioli | Interseção de Esferas no R n e Aplicações[END_REF], temos uma generalização de tal abordagem. Em ambos os casos se faz uso da álgebra linear, levando em conta estratégias eficazes para se resolver sistemas lineares associados a (1.1), através da fatoração LU e da decomposição QR [START_REF] Meyer | Matrix Analysis and Applied Linear Algebra[END_REF][START_REF] Watkins | Fundamentals of Matrix Computations[END_REF].

Dado um espaço vetorial W , dizemos que o conjunto de vetores V = {v 1 , . . . , v p }, com cada v i ∈ W , para i = 1, . . . , p, é linearmente independente (L.I.) quando temos p i=1 α i v i = 0 se, e somente se, α 1 = • • • = α p = 0. Quando V não é L.I., dizemos que V é linearmente dependente (L.D.).

Dado um espaço vetorial W , dizemos que o conjunto de vetores V = {v 1 , . . . , v p }, com cada v i ∈ W , para i = 1, . . . , p, é afim independente (A.I.) quando 

k i=1 α i = 1, a i ∈ A, α i ∈ R, k ≤ p    .
Ou seja, aff(A) é a interseção de todos os subespaços afins que contêm A, i.e., o menor subespaço afim que contém A.

Outro resultado usado com frequência ao longo deste trabalho é que um conjunto {x 1 , . . . , x p-1 , x p } ⊆ R n é A.I. se, e somente se, {x 1 -x p , . . . , x p-1 -x p } é L.I.

Aplicação no problema de geometria molecular

O PDB (do inglês, Protein Data Bank) [START_REF] Berman | The protein data bank[END_REF] é uma base de dados de estruturas moleculares 3D de proteínas. Esta base possui inúmeras informações catalogadas sobre tais moléculas, sendo uma fonte bastante utilizada por pesquisadores da área.

Comumente, para se obter informações microscópicas sobre moléculas são realizados experimentos através de uma das duas técnicas: raios X; ou ressonância magnética nuclear (RMN). Uma característica da primeira técnica é que esta fornece a estrutura 3D de alguns tipos de moléculas, mas necessita a cristalografia. O processo de cristalografia é bastante complexo e requer a desidratação da molécula. Embora experimentos de RMN não necessitem da cristalografia, estes fornecem distâncias apenas entre pares de átomos separados por não mais do que 6 Å [START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF][START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF]. Dependendo das características químicas da molécula de interesse, uma das técnicas pode ser mais vantajosa do que a outra. Ressaltamos que há moléculas em que informações determinantes podem ser perdidas caso esta sofra desidratação. No PDB temos dados de problemas reais vindos tanto de experimentos de RMN quanto de raio X para moléculas de proteínas. Neste trabalho levaremos em conta os dados provenientes dos experimentos de RMN. Figura 1 -Exemplo de proteína no PDB: ID 2IQH, Influenza A [START_REF] Berman | The protein data bank[END_REF].

Uma característica das moléculas de proteína é que sua função está intimamente relacionada com sua conformação geométrica. Tendo algumas distâncias entre pares de átomos de uma molécula, obtidas por experimentos de RMN, o problema consiste em determinar a estrutura 3D correspondente às distâncias disponíveis. Esse problema tem sido estudado com bastante eficiência através da abordagem apresentada em [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF][START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF]. Dados experimentais de RMN são esparsos e com ruídos [START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF]. Ou seja, as distâncias fornecidas pelas técnicas dos experimentos de RMN como dados de entrada são poucas se comparado ao número total de átomos a serem determinados. Além disso, as poucas distâncias disponíveis como entrada possuem incertezas. Isso traz dificuldades consideráveis ao problema inicial [START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF]. Notemos que o problema de determinar a estrutura 3D de uma proteína envolve diferentes áreas do conhecimento, entre elas: química, matemática, computação e biologia.

Há inúmeras possibilidades para formulação do problema matemático de se determinar a estrutura de moléculas a partir da situação real, assim como em outros processos de modelagem. Ao longo deste trabalho, vamos explorar os problemas associados ao conhecido Problema de Geometria de Distâncias Moleculares (PGDM). Estaremos nos referindo a tal problema na versão em inglês, i.e., como Molecular Distance Geometry Problem, ou simplesmente MDGP [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF]. Este problema é uma das mais relevantes aplicações da geometria de distâncias [START_REF] Blumenthal | Theory and applications of distance geometry[END_REF][START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF].

Alguns aspectos qualitativos e quantitativos das proteínas. Derivada do grego proteis (primeiro, primitivo), a proteína é conhecida como a "molécula da vida". Isto condiz com o fato de praticamente todos organismos vivos possuírem tais moléculas. As proteínas são macromoléculas formadas por cadeias de aminoácidos, sendo estes conectados a seus vizinhos pelas ligações peptídicas. Um total de vinte aminoácidos se combinam para formar as proteínas conhecidas. Cada aminoácido tem uma estrutura fundamental, diferenciando-se um dos outros apenas por suas cadeias laterais. As informações aqui apresentadas para proteínas podem ser encontradas maior detalhes em [START_REF] Nelson | Lehninger Principles of Biochemistry[END_REF][START_REF] Berman | The protein data bank[END_REF][START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF][START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF].

A fim de ilustrar alguns aspectos quantitativos a serem levados em conta na tentativa de se construir um modelo matemático para encontrar a estrutura molecular a partir de alguns dados conhecidos a priori, destacamos que uma proteína pode conter milhares de moléculas de aminoácidos. Na prática uma molécula de proteína costuma ter mais do que 10 mil átomos.

Um aspecto importante para distinguir as proteínas uma das outras é sua conformação geométrica. Dessa maneira, mesmo que duas proteínas possuam os mesmos átomos e mesma quantidade de ligações peptídicas, podem ter funções diferentes, pois sua funcionalidade está intimamente associada a sua geometria, i.e., a sua estrutura geométrica espacial 3D. Diante das inúmeras possibilidades envolvidas na busca de determinar a conformação de uma proteína, percebemos que esse problema é um tanto amplo e complexo. É comum se referir a esse problema como cálculo de estruturas moleculares.

Figura 2 -Algumas informações sobre uma molécula de proteína [START_REF] Nelson | Lehninger Principles of Biochemistry[END_REF].

O backone da proteína. Na Figura 1 vemos partes da estrutura de uma molécula de proteína. Notemos que certas partes são enoveladas e outras são mais esticadas. A fim de tornar mais rigorosa a análise de problemas de aplicação é comum considerarmos certas hipóteses. Uma hipótese assumida ao longo deste trabalho é que estamos lidando somente com os átomos da cadeia principal, o conhecido backbone. O backbone de uma proteína é formado pela sequência dos átomos N-C α -C que se repetem ao longo de toda molécula. A imagem à direta na Figura 1 ilustra o backbone de uma proteína catalogada no PDB [START_REF] Berman | The protein data bank[END_REF] e identificada por 2IQH. Já a Figura 2 ilustra parte do backbone com alguns átomos das cadeias laterais. Uma vez determinado o backbone, é possível obter outros átomos na molécula de proteína através de suas propriedades químicas. Ainda nesse sentido, analisando as características de uma molécula, é possível saber de antemão as distâncias entre alguns dos seus pares de átomos, além de certos ângulos com interesse especial. Mais detalhes podem ser encontrados em [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF][START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF].

Sobre experimentos computacionais.

Quando construímos instâncias para testar um modelo proposto, muitas vezes estamos lidando com o backbone. Embora isso pareça uma limitação, as instâncias geradas englobam várias características das moléculas de proteínas.

Por exemplo, há partes da molécula que são mais rígidas se comparado a outras partes. Em geral, tal parte está associada a ligação peptídica, que leva ao conhecido plano peptídico. As Figuras 1 e 2 ilustram essas características.

Na prática as moléculas de proteína estão inseridas em um meio físico, onde inúmeros fatores influenciam a posição de seus átomos. Sendo assim, questões envolvendo a temperatura e energia naturalmente contribuem na conformação molecular. Ao longo deste trabalho, não investigaremos esses fatores. Maiores detalhes sobre tais questões podem ser encontrados em [START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF]. O problema que temos em vista neste trabalho é o MDGP e suas variações levando em conta o efeito dos erros de medidas experimentais.

Modelando o problema de geometria molecular. A fim de apresentarmos os principais problemas que vamos abordar via AGC, nos concentremos no problema do cálculo da estrutura 3D de uma molécula, a partir de algumas distâncias conhecias entre alguns de seus pares de átomos [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF][START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF][START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF]. Em [START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF] há informações sobre o problema de interseção de esferas em que se investiga aspectos como a área e o volume resultante das interseções no contexto de modelagem molecular. Aqui focaremos nos aspectos descritos a seguir.

Em uma primeira abordagem assumimos que todas as distâncias disponíveis são precisas, i.e., não possuem erro experimental associado. Sob tal condição, é possível resolver o problema pelo método exato conhecido como algoritmo Branch and Prune (BP) [START_REF] Liberti | A branch-and-prune algorithm for the molecular distance geometry problem[END_REF]. O passo central do algoritmo BP é realizar a interseção de três esferas. O processo de poda ocorre quando há distâncias extras, além das três usuais, no nível analisado. Matematicamente, a interseção de três esferas S i (a i , r i ) no R 3 de centros a i e raios r i , para i = 1, 2, 3, é o conjunto dos pontos x ∈ R 3 satisfazendo o seguinte sistema de equações não-lineares:

         ||x -a 1 || = r 1 , ||x -a 2 || = r 2 , ||x -a 3 || = r 3 .
Sob condições adequadas [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF], o resultado da interseção de três esferas é dois pontos. Este resultado ocorre na maioria das aplicações e está associado à posição dos centros e aos raios das esferas. Neste trabalho assumiremos que os centros das esferas podem ser L.I., A.I. ou quaisquer. Na figura acima vemos que a posição dos centros das esferas é de grande importância para investigarmos as possíveis soluções do problema de interseção de esferas. A direita, no plano cartesiano, temos um contra-exemplo de um conjunto que é A.I., mas não é L.I.

Os dados de entrada do nosso problema de geometria molecular é um conjunto de átomos V e um conjunto de distâncias {d i,j } entre alguns dos átomos. Como as informações rotulam a quais átomos correspondem às distâncias, temos um conjunto de arestas E que informam os pares de átomos correspondentes às distâncias d i,j . Matematicamente, a função distância é definida por d :

E → R + , sendo d(v i , v j ) = d i,j
. Dessa maneira, os dados de entrada podem ser representados por um grafo G = (V, E, d). Usaremos a notação x(v i ) = x i para denotar a realização de um vértice no R 3 e d i,j para d(v i , v j ), i.e., para distância entre o par de vértices (átomos) v i e v j . Essa realização de um vértice corresponde a suas coordenadas retangulares no R 3 . Por exemplo, afirmar que foi obtida uma realização x para o vértice v i , equivale a ter definido a função x :

v i → x(v i ) = (x 1 i , x 2 i , x 3 i ) = x i ∈ R 3 .
Uma realização como esta também é chamada de realização válida, ou realização parcial.

Definição (MDGP). Dado um grafo simples G = (V, E, d), conectado e ponderado nas arestas por

d : E → (0, ∞), encontre uma função x : V → R 3 tal que, para todo {v i , v j } ∈ E, ||x(v i ) -x(v j )|| = d i,j .
Em geral, abordagens tradicionais de otimização são inviáveis para resolver o MDGP, pois estamos diante de um problema inverso de otimização global não-linear, onde o número de mínimos locais aumenta exponencialmente em função do número de vértices |V | = n. Destacamos que este é um problema NP-difícil [START_REF] Saxe | Embeddability of graphs in k-space is strongly NP-hard[END_REF]. Dessa maneira, é esperado nos depararmos com diversas dificuldades. Uma delas é que procuramos por mínimos globais e temos uma grande quantidade de mínimos locais. Isso dificulta consideravelmente utilizarmos métodos tradicionais de otimização [START_REF] Griva | Linear and Nonlinear Optimization[END_REF].

Consideremos a tentativa de resolver o problema usando o método de Newton [START_REF] Griva | Linear and Nonlinear Optimization[END_REF]. Como este método fornece uma solução local, poderíamos tentar usá-lo iterativamente para obter as várias soluções locais, que são mínimos locais. Em seguida teríamos que procurar por mínimos globais. Para uma molécula com |V | = 10 átomos, nosso espaço de busca é o R 30 , o que dificulta a procura por todos os mínimos locais. Sob tal abordagem, para encontrar uma solução utilizando os computadores disponíveis na atualidade seríamos levados a um tempo de processamento muito grande, mais do que algumas décadas. Como a solução do MDGP é um mínimo global, pode ser inviável partir por essa abordagem. Na prática, as moléculas de proteína chegam a ter mais do que 10 mil átomos. Portanto, há a necessidade de novas ferramentas para tratar esse problema.

Abordagem combinatória. De posse de uma ordem sobre os vértices do MDGP, é possível discretizar o problema obtendo o DMDGP, Discretizable Molecular Distance Geometry Problem [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF]. Para este novo problema podemos aplicar o algoritmo BP [START_REF] Liberti | A branch-and-prune algorithm for the molecular distance geometry problem[END_REF] para encontrar todas as soluções do problema.

Definição (DMDGP). Considere o grafo

G = (V, E, d) de um MDGP e uma ordem em V , denotada por v 1 , . . . , v n , tal que (i) existe uma realização válida para v 1 , v 2 , v 3 ; (ii) para todo v i , onde i = 4, . . .

, n, existem três vértices imediatamente anteriores

v i-3 , v i-2 , v i-1 , com {{v i-3 , v i }, {v i-2 , v i }, {v i-1 , v i }} ⊆ E, satisfazendo d(v i-3 , v i-2 ) + d(v i-2 , v i-1 ) > d(v i-3 , v i-1 ). Encontre uma função x : V → R 3 , tal que ||x(v i ) -x(v j )|| = d i,j , para todo {v i , v j } ∈ E.
Tendo obtido uma ordem sob os vértices no MDGP, é possível explorar de forma eficiente o grafo associado, atribuindo uma estrutura adequada ao espaço de busca. No entanto, encontrar uma ordem para o MDGP não é trivial. Pelo contrário, também é um problema NP-díficil. Sendo assim, embora de posse de uma ordem sobre os átomos a resolução do problema seja simplificada, há um alto custo computacional para se encontrar essa ordem [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF][START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF][START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF].

Aplicações envolvendo espaços nD

O Problema da Matriz de Distâncias Euclideanas (PMDE). De posse de uma matriz simétrica D de ordem n × n cuja diagonal principal seja nula, o PMDE consiste em saber se existem pontos {x 1 , . . . , x n } ⊆ R K , para algum número inteiro K > 0, satisfazendo

||x i -x j || = D(i, j), ( 1.2) 
para todo i, j = 1, . . . , n, onde D(i, j) denota a entrada (i, j) da matriz D. Neste problema, além de não conhecermos a posição dos vértices no espaço Euclideano R K , não conhecemos a dimensão K do espaço onde procuramos a realização do grafo associado aos dados de entrada. No caso de termos como entrada todos elementos da matriz D, conforme (1.2), podemos resolver o problema através da estratégia mostrada em [START_REF] Alencar | An algorithm for realizing Euclidean distances matrices[END_REF], onde se usa a abordagem clássica, i.e., baseada em álgebra linear, para realizar a interseção de n esferas no R n . Neste caso, a matriz D é denominada matriz de distâncias Euclideanas. Já para o caso de dispormos de apenas algumas das entradas de D, uma tentativa é seguir [START_REF] Maioli | Interseção de Esferas no R n e Aplicações[END_REF] para obter a interseção de m esferas no R n . Nesse caso mais geral, podem surgir erros numéricos que trazem limitações na busca de uma solução. Este novo problema é conhecido como problema de completamento da matriz de distâncias Euclideanas. Detalhes sobre tais problemas podem ser encontrados em [START_REF] Alencar | An algorithm for realizing Euclidean distances matrices[END_REF][START_REF] Maioli | Interseção de Esferas no R n e Aplicações[END_REF][START_REF] Datorro | Convex Optimization & Euclidean Distance Geometry[END_REF].

Problemas de Escalamento Multidimensional (MDS).

Técnicas de MDS (do inglês, multidimensional scaling) têm sido usadas para se visualizar conjunto de dados. Comumente, os dados de entrada para problemas envolvendo MDS são medidas de proximidade entre pares de objetos, mais especificamente, medidas de dissimilaridade entre pares de objetos. Os dados de entrada em tal contexto muitas vezes estão em espaços de dimensão muito alta, o que impossibilita extrair-se informações tratando os dados no espaço de origem. Nesse sentido, o problema consiste em representar os pontos correspondentes aos dados de entrada em um espaço de baixa dimensão de forma que as informações iniciais continuem presentes na nova representação. Obter uma visualização dos dados em baixa dimensão viabiliza a possibilidade de analisarmos informações presentes no conjunto de dados de entrada de maneira adequada.

Como exemplo, digamos que os objetos i e j possuam n atributos que desejamos analisar. Tais atributos podem ser o preço, a durabilidade, a funcionalidade, entre outras características. Os dados de entrada do problema podem ser representados como uma matriz D = δ ij de ordem n × n, onde δ ij denota a medida de dissimilaridade entre i e j, sendo interpretada como a distância entre i e j. O valor de δ ij é uma quantidade empírica associada aos objetos i e j. O problema consiste em encontrar o conjunto

{x i } m i=1 ⊆ R n solução de min δ ij - i,j ||x i -x j || 2 .
(1.3) Notemos que na expressão acima as quantidades x i = (x i 1 , . . . , x in ) e x j = (x j 1 , . . . , x jn ) são estimadas a partir dos dados de entrada do problema, i.e., da dissimilaridade dada por δ ij . Os valores x i k e x j k , isto é, a coordenada k de x i e x j , respectivamente, denotam a quantidade do atributo k que os objetos i e j possuem. Tendo uma solução para este problema, podemos visualizar os atributos relacionados entre cada par de objetos disponíveis, além de investigar diferentes aspectos do conjunto de dados em questão. Encontrar {x i } m i=1 ⊆ R n , equivale a obter uma representação em baixa dimensão para o problema. Esta é obtida por uma realização do grafo associado ao problema de distância determinado pela matriz D, sendo que não conhecemos a dimensão do espaço onde procuramos tal realização, mas sabemos as medidas de dissimilaridades δ ij entre os vértices. Dependendo das particularidades dos dados de entrada correspondentes às dissimilaridades, devemos reformular a função objetivo em (1.3). Em [START_REF] Davison | Multidimensional scaling[END_REF] é possível encontrar mais detalhes sobre o assunto.

Distâncias com incertezas no cálculo de estruturas moleculares

Acrescentando uma casca esférica ao problema inicial. Encontrar a solução da interseção entre m esferas e uma casca esférica no R n equivale a resolver:

       ||x -a i || = d i , i = 1, . . . , m, d m+1 ≤ ||x -a m+1 || ≤ d m+1 , (1.4) 
onde a segunda equação representa a casca esférica que acrescentamos ao problema inicial (1.1). Uma maneira eficiente de modelar as incertezas presentes em dados experimentais é por meio de cascas esféricas. Nos Capítulos 4 e 5 veremos que o método apresentado via AGC para interseção de esferas no caso 3D pode ser estendido para lidarmos com mais do que uma casca esférica, enquanto que a abordagem convencional se torna inviável para esse caso.

O efeito das incertezas experimentais. Em um primeiro momento, as análises aqui feitas levam em conta que as distâncias disponíveis não possuem incertezas. Em uma próxima etapa, desejamos incorporar em nosso modelo matemático o efeito das incertezas presentes nas medidas vindas dos experimentos de RMN. Na prática é comum haver um erro associado às medidas de distâncias experimentais, visto que o aparelho usado na captura dos dados tem suas limitações físicas. Uma maneira de considerar incertezas nas distâncias disponíveis, usadas como dados de entrada do DMDGP, é assumindo que algumas delas pertençam a certos intervalos, tendo assim uma cota superior e uma inferior. Neste caso, podemos representar as incertezas supondo que as distâncias

d i-3,i pertençam ao intervalo [d i-3,i -δ, d i-3,i + δ],
onde δ é um número real positivo. Lembremos que algumas distâncias podem ser determinadas a priori através da análise das propriedades químicas da molécula. Sendo assim, podemos assumir que as distâncias d i-2,i e d i-1,i são precisas (sem erros de medição), enquanto que d i-3,i é intervalar, i.e., imprecisa (com erros de medição). Tal hipótese é adequada para o problema real e tem se verificado ao longo das pesquisas na área [START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF][START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF][START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF]. Figura 4 -Ilustração de uma das etapas do algoritmo BP [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF].

Ressaltamos que cada iteração do BP feita para obter a realização parcial do vértice v i equivale, geometricamente, à interseção de três esferas no R 3 . Isso fornece como solução dois pontos no R 3 , i.e., temos duas possibilidades para cada realização parcial de v i . Enquanto a Figura 4 ilustra a discretização no caso em que as distâncias envolvidas não possuem erros, a figura abaixo mostra o efeito de se levar em conta as incertezas experimentais. Assumindo d i-3,i intervalar, agora a cada tentativa de realizar um vértice v i temos o problema de encontrar a interseção entre duas esferas e uma casca esférica no R 3 , conforme vemos na Figura 5. Logo, ao invés de termos dois pontos como resultado da interseção, i.e., duas possibilidades para a posição de v i , passamos a ter dois arcos. Ou seja, temos dois intervalos de possibilidades para a posição do átomo v i , quando nosso problema incorpora incertezas.

Figura 5 -Ilustração de uma das etapas do algoritmo iBP [START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF].

No caso de assumirmos a possibilidade de distâncias intervalares nos dados de entrada, podemos usar uma nova versão do BP para tratar este novo problema. A saber, o algoritmo iBP (do ingês, interval Branch and Prune) [START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF]. O algoritmo iBP é uma extensão do BP, e permite lidar com as distâncias imprecisas. De forma geral, o iBP busca resolver o problema da perda de discretização da árvore BP através de uma amostragem adequada dos intervalos de possibilidades, permitindo a descida na árvore. Porém, em tal abordagem, entre outros fatores, a propagação de erros a cada iteração pode tornar o problema inviável. Além disso, não temos uma garantia de que a amostragem escolhida sempre é adequada para assegurar que uma solução seja encontrada conforme se desce nos níveis da árvore iBP. Mesmo sob sucessivos refinamentos na amostragem, não conseguimos condições para assegurar que uma solução seja sempre encontrada.

Uma proposta para lidar com o problema de assumir d i-3,i intervalar, é usar o algoritmo iBP em conjunto com a AGC [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF][START_REF] Alves | Álgebra de Clifford Aplicada ao Cálculo de Estruturas Moleculares[END_REF]. Com isso, é possível evitar o processo de amostragem e garantir a descida na árvore do BP sem tornar o problema inviável, garantindo uma classe de soluções para tal problema. Essa abordagem vem sendo explorada recentemente sob diferentes pontos de vista. Uma generalização possível em tal abordagem é a busca de incorporar distâncias imprecisas não somente em d i-3,i , mas em outras distâncias de entrada do problema.

Álgebra geométrica conforme (AGC)

Seguindo [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF][START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for computer vision and graphics[END_REF][START_REF] Dorst | Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[END_REF][START_REF] Fernandes | Álgebra Geométrica e Aplicações[END_REF][START_REF] Hildenbrand | Foundations of Geometric Algebra Computing[END_REF][START_REF] Li | Computational geometry 2: Generalized coordinates for computational geometry[END_REF][START_REF] Hitzer | Introduction to Clifford's Geometric Algebra[END_REF][START_REF] Perwass | Geometric algebra with applications in engineering[END_REF], vejamos alguns elementos da álgebra geométrica conforme (AGC) bastante úteis para lidar com aplicações da geometria de distâncias. Nos próximos capítulos usaremos as definições e conceitos aqui apresentados. Embora alguns resultados sejam usuais na literatura, outros foram derivados de forma a se adequarem ao problema de interseção de esferas.

Definições preliminares

Um espaço vetorial V sobre o corpo de escalares R é uma álgebra se está definida sobre seus elementos x, y, ∈ V uma operação de multiplicação, denotada por xy, satisfazendo:

(i) α(xy) = (αx)y = x(αy) (associatividade de escalares), (ii) (xy)z = x(yz) (associatividade), (iii) (x + y)z = xz + yz (distributividade), para todo x, y, z ∈ V e α ∈ R. Se a multiplicação é comutativa, i.e., se xy = yx para todo x, y ∈ V , então dizemos que a álgebra é comutativa. Se V tem dimensão n quando considerado como espaço vetorial, dizemos que a álgebra tem dimensão n.

Observações. O corpo de escalares R na definição acima poderia ser outro, como por exemplo, o conjunto dos números complexos C. No entanto, neste trabalho lidamos apenas com o caso de escalares em R. Como de costume, denotaremos por e i , para i = 1, . . . , n, os elementos da base canônica do espaço Euclideano R n .

A álgebra de Grassmann no R n é a álgebra gerada por 1, e 1 , . . . , e n e operação de multiplicação ∧ que é associativa, distributiva e verifica o seguinte: e i ∧ e i = 0, e i ∧ e j = -e j ∧ e i , onde i, j = 1, . . . , n. Esta álgebra é um espaço vetorial com respeito a soma e multiplicação por escalar, cuja dimensão é 2 n . O produto denotado por ∧ é denominado produto exterior, ou produto de Grassmann1 .

A álgebra de Clifford no R n é a álgebra gerada por 1, e 1 , . . . , e n e operação de multiplicação denotada pela justaposição que é associativa, distributiva e satisfaz: e 2 i = 1, e i e j = -e j e i , onde i, j = 1, . . . , n. Este produto é conhecido como produto geométrico ou produto de Clifford. Esta álgebra é um espaço vetorial de dimensão 2 n , com respeito a soma e multiplicação por escalar.

O espaço vetorial associado à álgebra de Clifford no R n pode ser visto como um espaço multivetorial R n definido por Os elementos de R n são os conhecidos multivetores. Um multivetor ξ ∈ R n é formado pela combinação linear de k-vetores de grau k = 0 a k = n. Podemos escrever isso como Representando subespaços por blades. A partir do produto exterior, é possível interpretarmos blades como sendo subespaços vetoriais. Isso permite realizarmos operações entre dois subespaços através de operações da AGC de forma direta. O conceito de blade generaliza o conceito de subespaços, pois, além de fornecer informações sobre o subespaço vetorial, é capaz de codificar a noção de orientação e magnitude do objeto geométrico o qual representa. Por exemplo, e 1 ∧ e 2 denota um plano orientado de acordo com a regra da mão direita. Já que e 1 e e 2 estão associados a subespaços de dimensão 1, i.e., retas cujo vetor suporte são tais vetores, então o subespaço obtido com o produto exterior entre estes tem dimensão 2. A posição relativa entre estes vetores está relacionada à informação disponível sobre a sua orientação. Como veremos adiante, através de relações de dualidade, podemos realizar a interseção entre subespaços utilizando o produto exterior. Quando analisamos a interseção de subespaços, a orientação dos subespaços envolvidos é indispensável. Por exemplo, se temos dois planos no R 3 passando pela origem e ambos não são paralelos, a interseção entre estes fornece uma reta como resultado. Por outro lado, se tais planos forem paralelos o resultado é um plano. Isso mostra que a interseção está intimamente ligada à orientação dos objetos a serem intersectados.

R n = 0 R n ⊕ 1 R n ⊕ • • • ⊕ n R n , ( 2 
ξ = α 0 ξ 0 + α 1 ξ 1 + • • • + α n ξ n = n k=1 α k ξ k , ( 2 
Produto exterior a partir do produto geométrico. O produto geométrico é definido de forma a generalizar as propriedades do produto exterior. Nesse sentido, é desejável que tal produto codifique de forma compacta a noção de orientação e outras características geométricas fundamentais. De fato, o produto geométrico é bastante geral, permitindo que através dele possamos recuperar o produto exterior ∧ e, até mesmo, definir novos produtos. Uma maneira de recuperar o produto exterior entre dois blades

ξ 1 ∈ k R n e ξ 2 ∈ l R n através do produto geométrico é por ξ 1 ∧ ξ 2 =        ξ 1 ξ 2 k+l , se k + l ≤ n, 0, se k + l > n.
(2.3) Ou seja, podemos obter ξ 1 ∧ ξ 2 se realizarmos o produto geométrico entre ξ 1 e ξ 2 e, após isso, extrairmos o grau k + l do blade obtido. Ressaltamos que a extração do grau k tem custo computacional escalar, pois basta analisarmos no blade resultante2 qual de suas componentes correspondem à dimensão do blade esperado. Esse processo se resume em percorrer cada uma das componentes, análogo ao que fizemos em (2.2).

Produtos internos. Seguindo a mesma estratégia usada para definirmos o produto exterior em (2.3), definimos o produto interno entre

ξ 1 ∈ k R n e ξ 2 ∈ l R n por ξ 1 • ξ 2 =                ξ 1 ξ 2 l-k , para k < l, ξ 1 ξ 2 0 , para k = l, ξ 1 ξ 2 k-l , para k > l.
(2.4) Cada caso envolvendo k e l na definição acima leva a uma interpretação geométrica. Se l > k, o produto interno ξ 1 • ξ 2 indica que estamos realizando uma contração à esquerda de ξ 1 e ξ 2 . Isto equivale a retirar de ξ 2 a parte que seja mais parecida com ξ 1 . O resultado é um blade de grau l -k que está contido em ξ 2 e é perpendicular a ξ 1 . A contração à esquerda costuma ser denotada por ξ 1 ξ 2 . De forma análoga, temos a contração à direita, denotada por ξ 1 ξ 2 , quando k > l. Já quando k = l, obtemos como resultado um escalar. Ressaltamos que (2.4) ou seus subcasos aqui mencionados são produtos internos não-Euclideanos. Adiante veremos mais detalhes sobre este aspecto. Outra característica em (2.4) é que se k > l, então ξ 1 ξ 2 l-k = ξ 1 ξ 2 = 0, indicando que o resultado não existe. Ou seja, a contração à esquerda se anula, pois estaremos retirando de ξ 2 , via contração, um subespaço de dimensão maior do que a deste. Uma análise semelhante a esta vale para os demais casos em (2.4), indicando a não existência do resultado obtido na operação.

A equação fundamental da AGC. De posse do produto geométrico, definimos o produto exterior e o produto interno entre dois blades de grau 1, denotados por a e b,

a • b = 1 2 ab + ba , a ∧ b = 1 2 ab -ba .
Das identidades acima segue a equação fundamental da AGC:

ab = a • b + a ∧ b. (2.5)
A identidade (2.5) pode ser generalizada para lidar com blades de grau k arbitrário. Além disso, as definições para o produto exterior, interno e geométrico podem ser definidas para multivetores. Em ambas generalizações, os resultados se baseiam na expressão (2.2) e no fato que tais produtos são bilineares. Como a princípio, ao longo deste trabalho, não estaremos lidando com multivetores de grau misto, mas sim com blades, as definições vistas fornecem o embasamento necessário para nosso trabalho. Caso surjam situações específicas que fujam dos elementos apresentados, buscaremos introduzir os pré-requisitos necessários.

O espaço conforme

Dizemos que R n+1,1 é o espaço vetorial constituído por uma parte Euclideana e uma conforme, denotadas, respectivamente, por R n e R Isto porque e 2 0 = e 0 • e 0 = 0, sendo e 0 = 0. Em [START_REF] Li | Computational geometry 2: Generalized coordinates for computational geometry[END_REF] se mostra que R n+1,1 admite a seguinte decomposição:

R n+1,1 = R n ⊕ R 1,1 .
Esta decomposição indica uma imersão do espaço Euclideano R n no espaço conforme R n+1,1 . Sendo assim, os elementos no espaço conforme R n+1,1 podem ser expressos em termos da base ortogonal {e 0 , e 1 , . . . , e n , e ∞ }. Agora a relação de ortogonalidade passa a ser em termos do produto interno (2.4). Destacamos que, no caso de estarmos lidando apenas com elementos Euclideanos, i.e., vetores do R n , o produto interno aqui definido atua da mesma maneira que o produto interno canônico Euclideano.

Elementos do espaço conforme

Os pontos p em R n+1,1 satisfazem as duas condições:

a) p • e ∞ = -1, (2.11) b) p 2 = 0. (2.12)
As equações em a) e b) equivalem a termos uma forma padrão para representar os pontos

x = n i=1 α i e i ∈ R n , onde α i ∈ R, no espaço conforme R n+1,1
, pois estas asseguram que

p = e 0 + x + 1 2 ||x|| 2 e ∞ .
(2.13)

A expressão (2.13) é conhecida como representação primal em R n+1,1 do ponto x ∈ R n . Assumiremos que esta é a representação padrão dos pontos no espaço conforme.

A distância Euclideana entre os pontos p e q em R n+1,1 é definida por

d E (p, q) = 2 |p • q|. (2.14)
Propriedades do produto interno (2.4). Dado dois pontos p e q em R n+1,1 , representações de p e q do R n , o produto interno entre estes pode ser expresso por

p • q = - 1 2 ||q -p|| 2 .
(2.15)

A identidade acima mostra que o produto interno na AGC é proporcional ao quadrado da distância entre os pontos, com um fator negativo. Isso está associado ao fato do produto interno ser não-Euclideano, pois no caso Euclideano a distância entre dois pontos sempre é não-negativa.

O produto interno verifica as seguintes propriedades:

e i • e j = δ ij , e 0 • e i = 0, e ∞ • e i = 0, e 2 0 = e 2 ∞ = 0, e 0 • e ∞ = -1, onde i, j = 1, . . . , n e e 2 i denota e i e i = e i • e i .
Definições envolvendo k-blades em espaços nD. Quando lidamos com k-blades em espaços nD, i.e., de dimensão n, as manipulações algébricas estão intimamente ligadas com as dimensões e graus envolvidos. Por exemplo, na definição de produto interno, lidamos diretamente com o grau dos blades envolvidos. Além disso, ao definirmos o dual de um blade é preciso tomarmos cuidado com a dimensão dos subespaços envolvidos. Nas definições a seguir veremos como este aspecto aparece na AGC. Em particular, quando definimos as operações de join e meet é preciso uma atenção especial ao subespaço subjacente ao problema.

O reverso V de um blade V de grau k é definido por

V = (-1) k(k-1) 2 V. (2.16)
O efeito do reverso é de inverter a ordem de um blade no seguinte sentido. Digamos que o k-blade V é fatorado da seguinte maneira

V = v 1 ∧ • • • ∧ v k .
Então,

V = (-1) k(k-1) 2 v 1 ∧ • • • ∧ v k = v k ∧ • • • ∧ v 1 . Notemos que ( V ) = V.
Outra operação bastante usual nas manipulações algébricas é a involução do grau. A involução do grau V de um blade V de grau k é definida por

V = (-1) k V.
(2.17)

De posse da involução do grau podemos escrever uma generalização das identidades envolvendo a equação fundamental da AGC (2.5) para o caso de termos um 1-blade e um k-blade denotados por a e B, respectivamente:

a • B = 1 2 aB -Ba , a ∧ B = 1 2 aB + Ba , e aB = a • B + a ∧ B.
Definimos a inversa de um blade V como

V -1 = V ||V || 2 = V V • V . (2.18)
Aqui usamos a definição de norma reversa ao quadrado

||V || 2 = V • V . Na definição de inversa de um blade assumimos que ||V || = 0. Se ||V || = 0, dizemos que o blade V não tem inversa. O dual de um blade V em R n+1,1 é definido por V * = V I = V I -1 = (-1) n(n-1) 2 V I, onde I é o pseudoescalar do R n+1,1 , definido por I = e 0 e 1 . . . e n e ∞ = e 0 ∧ e 1 ∧ • • • ∧ e n ∧ e ∞ .
A noção de dualidade na AGC é análoga à de complemento ortogonal conhecida da álgebra linear, no sentido de que dado um espaço vetorial U de dimensão n e um subespaço vetorial W de U , com dimensão k, então o dual de W é um subespaço de U ortogonal a W , cuja dimensão é n -k. Além disso, na AGC o conceito de dualidade também codifica a magnitude e orientação do subespaço dual. Esta característica permite que as manipulações algébricas entre os blades sempre estejam bem definidas. Quando lidarmos com a interseção de esferas, veremos como é importante saber a orientação e magnitude dos subespaços obtidos ao longo das sucessivas interseções.

Outra característica do conceito de dualidade no modelo conforme é que podemos optar por trabalhar com os elementos da AGC representados na forma direta ou na forma dual, de acordo com a necessidade do nosso problema. Para obter a expressão Euclideana do blade V na forma dual, devemos encontrar todos os pontos x ∈ R n , representados por p ∈ R n+1,1 , tais que

p • V = 0. (2.19)
Já quando V estiver na forma direta, usamos

p ∧ V = 0. (2.20)
Ao longo deste trabalho vamos lidar na maioria das vezes com a representação dual dos objetos Euclideanos no espaço conforme. A escolha de uma representação adequada permite tratar o problema sob pontos de vista diferentes de forma eficiente.

Na AGC é possível alterarmos da representação dual para a primal através da operação de desdualização. A desdualização de um blade V em R n+1,1 é definida por

V - * = V I, onde I é o pseudoescalar do R n+1,1 .

Relações de dualidade.

Enquanto o produto exterior independe da métrica, os produtos internos aqui definidos são métricos. Dependendo da operação que estamos realizando, escolhemos uma métrica Euclideana para defini-los, de forma que possamos sempre fixar uma base ortogonal a fim de simplificar os cálculos e implementações computacionais. Por exemplo, quando definimos a contração à esquerda, podemos assumir que a métrica subjacente seja a Euclideana e que estamos de posse de uma base ortonormal visto que, no caso Euclideano, através do processo de Gram-Schmidt, é possível obtermos tal base no caso de subespaços de dimensão finita (vide Anexos).

Como o produto exterior entre duas esferas duais distintas 3 fornece a representação dual do resultado da interseção entre estas, optamos preferencialmente pela representação dual para lidar com as esferas. Tal escolha facilitou a interpretação geométrica ao lidarmos com a interseção. No entanto, em algumas definições, como por exemplo a do par de pontos, a notação primal se mostra mais adequada para entender a geometria do problema. A AGC fornece uma maneira de relacionar os produtos métricos e não-métricos em termos das representações dual e primal. As expressões abaixo mostram relações de dualidade que facilitam a interpretação dos conceitos que usaremos nos Capítulos 4 e 5.

Para todos os blades A e B, temos as seguintes relações:

(A ∧ B) * = A • (B * ), (A • B) * = A ∧ (B * ).
Temos também relações de dualidade envolvendo a contração à esquerda :

(A ∧ B) C = A (B C), (A B) C = A ∧ (B C) (válida quando A ⊆ C), para quaisquer blades A, B e C.
Independência linear via produto exterior. Podemos usar o produto exterior para estabelecer se um conjunto de vetores é L.I. ou não: o conjunto de vetores {v 1 , . . . , v p } é L.I. se, e somente se, v 1 ∧ • • • ∧ v p = 0. A demonstração deste resultado está nos Anexos.

Representação de esferas como vetores

Uma esfera do R n de raio r e centro c tem representação dual em R n+1,1 dada por

σ = c - r 2 2 e ∞ , (2.21) 
onde

c = e 0 + c + 1 2 ||c|| 2 e ∞ .
De fato, (2.21) é a representação dual da esfera no R n , pois para todo ponto p em R n+1,1 (2.13), temos

0 = p • σ = p • c - r 2 2 p • e ∞ = p • e 0 + c + ||c|| 2 2 e ∞ - r 2 2 e 0 • e ∞ = ||x|| 2 2 e ∞ • e 0 + x • c + ||c|| 2 2 e 0 • e ∞ + r 2 2 = - 1 2 ||x|| 2 + ||c|| 2 -2 x • c + r 2 2 = - 1 2 ||x -c|| 2 + r 2 2 , onde x ∈ R n . Portanto, pela expressão acima, obtemos ||x -c|| 2 = r 2 . (2.22)
Esta é a equação de uma esfera no R n de raio r e centro c. Notemos que quando r = 0, a equação acima se reduz a um ponto. Se r < 0, não temos solução real para (2.22), pois

x / ∈ R n . Em [START_REF] Dorst | Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[END_REF] este caso é denominado esfera imaginária. Aqui nos concentraremos ao caso real, i.e., quando r ≥ 0.

A esfera acima, (2.21), é definida de forma que seu raio r seja tal que

r 2 = σ 2 (σ • e ∞ ) 2 = - σ σ (e ∞ • σ) 2 , ( 2.23) 
onde σ indica a involução do grau de σ, conforme (2.17). Além disso, seu centro c pode ser obtido através de

c = r 2 2 e ∞ - σ σ • e ∞ .
Sob a forma padrão (2.21), as expressões acima para o raio e centro da esfera se reduzem a

r 2 = σ 2 , c = σ + r 2 2 e ∞ .
De posse da representação dual de uma k-esfera em R n+1,1 , denotada por σ (2.21), a esfera definida por Logo, σ n satisfaz a condição (2.11).

σ n = - σ e ∞ • σ ,
Figura 7 -Representação de objetos Euclideanos no espaço conforme.

Combinação linear em R n+1,1 . O resultado da combinação linear de dois pontos p e q em R n+1,1 dada por

α p + β q, (2.24)
onde α, β ∈ R, pode não resultar em um ponto, mas sim em uma esfera. Podemos verificar esse fato com auxílio das propriedades (2.11) e (2.12). Como

α p + β q 2 = α 2 p 2 + β 2 q 2 + 2αβ (p • q) = 2αβ (p • q), então α p + β q 2 e ∞ • α p + β q 2 = 2αβ (p • q) α + β 2 = 2αβ (p • q) = -αβ ||q -p|| 2 , se α + β = 1. Portanto, de acordo com (2.23), a combinação linear (2.24) com α + β = 1, é uma esfera cujo raio r satisfaz r 2 = -αβ d 2 E (p, q), sendo d E (p, q) definida por (2.14).
Embora (2.24) possa não resultar em um ponto, é possível escolhermos valores para os parâmetros α e β de forma que o resultado seja um ponto. Uma maneira de obtermos pontos como resultados da combinação linear é tratando os pontos envolvidos como flat, i.e., sendo obtidos como resultado da interseção entre uma reta e um plano. Algebricamente, isto significa tomar uma combinação linear da seguinte maneira

α p ∧ e ∞ + β q ∧ e ∞ .
No modelo conforme temos a distinção entre pontos flat e pontos finitos, visto que a maioria dos objetos na AGC estão intimamente relacionados com o aspecto geométrico. O ponto usual que definimos em (2.13), um ponto finito, é interpretado como uma esfera de raio nulo.

A interpretação geométrica de alguns conceitos quando vistos no espaço conforme podem ter significados diferentes dos conhecidos para o espaço Euclideano. No entanto, na AGC podemos lidar com as expressões de forma bastante próxima das construções geométricas usuais. Com a AGC a interpretação geométrica das operações aparece embutida nas manipulações algébricas de forma bastante natural.

Geometria no espaço conforme

Na geometria é comum o estudo de certas transformações definidas entre duas superfícies. De particular interesse é o estudo daquelas que preservam certas quantidades, das quais destacamos algumas [START_REF] Struik | Lectures on Classical Differential Geometry[END_REF]: conforme, a qual preserva ângulos; isométrica, a qual preserva distâncias e ângulos; equiareal, a qual preserva área.

Neste trabalho, as transformações mapeiam esferas em esferas sendo que o ângulo feito pelos planos tangentes nos pontos de interseção são preservados. Portanto, aqui, as transformações pertencem ao grupo das transformações conforme. No atual contexto, as transformações conforme podem ser definidas por versores, de forma que a reflexão é uma transformação básica, e a translação e rotação são obtidas pela composição de reflexões. Detalhes de como tais construções são feitas podem ser encontrados em [START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for computer vision and graphics[END_REF][START_REF] Dorst | Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[END_REF][START_REF] Perwass | Geometric algebra with applications in engineering[END_REF]. Definimos um versor como sendo os multivetores que podem ser fatorados como o produto geométrico de 1-vetores não-nulos. Assim, um versor V é definido por

V = v k v k-1 • • • v 1 , onde cada v i é um vetor em 1 R n .

Dizemos que o versor acima é um k-versor, pois é o produto geométrico de k vetores.

A inversa de um versor é dada por

V -1 = v -1 1 v -1 2 • • • v -1 k .
Em geral, um versor pode não ser um blade. Detalhes sobre a relação entre blades e versores podem ser encontrados em [START_REF] Perwass | Geometric algebra with applications in engineering[END_REF][START_REF] Dorst | Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[END_REF].

Na Figura 8 temos os versores mais usados ao longo dos nossos estudos. Essa forma de descrever uma rotação em um espaço 3D possui vantagens, se comparado com as tradicionais, principalmente com respeito as implementações computacionais. Nessa nova versão condensada, podemos generalizar diferentes conceitos e realizar deduções algébricas com maior nível de abstração, concentrando os esforços dedutivos não apenas em termos algébricos mas também em aspectos geométricos. Como já mencionamos, a inversão de um rotor é trivial. A saber, o inverso do rotor R (2.26), é dado por

R = cos θ 2 -sen θ 2 B, (2.26) onde B = a ∧ b sen(θ) , para sen(θ) = 0. Já no R 4,1 , o bivetor B em (2.26) é definido por B = π 1 ∧ π 2 ||π 1 ∧ π 2 || , onde π i , para i = 1,
R = cos θ 2 + sen θ 2 B.
Ou seja, obtemos o inverso de R apenas mudando um sinal em sua expressão.

Na tabela abaixo temos exemplos da representação de alguns objetos Euclideanos no espaço conforme.

O versor para translação. Na álgebra linear uma translação T b definida por

T b (x) = x + b (2.27)
atua de forma que, geometricamente, x é transladado por b para x = x + b. Na AGC obtemos x por meio de Um resultado interessante é que a translação

x = T b x T -1 b , ( 2 
T b = 1 - 1 2 be ∞ é tal que sua inversa é T -1 b = 1 + 1 2 be ∞ .
De fato, pelas propriedades (2.9) e (2.10), temos que

T b T -1 b = 1 - 1 2 be ∞ 1 + 1 2 b e ∞ = 1 + 1 2 be ∞ - 1 2 be ∞ - 1 4 be ∞ be ∞ = 1 + 1 4 be ∞ e ∞ b = 1.
Analogamente, mostramos que T -1 b T b = 1. Ou seja, para obtermos a inversa de T b basta mudarmos um sinal. Podemos verificar que o mesmo vale para os demais versores da Figura 8.

Representando isometrias por operações ortogonais. É conhecido que na álgebra linear [START_REF] Shilov | Linear Algebra[END_REF] não é possível representar a composição de translação, rotação e reflexão por meio de uma matriz, visto que a translação não é uma transformação linear. Por outro lado, com a AGC isto é possível.

Dizer que uma transformação conforme definida pelo versor V é uma isometria equivale a dizer que

Vξ 1 V -1 • Vξ 2 V -1 = ξ 1 • ξ 2 , para todo ξ 1 , ξ 2 ∈ R n+1,1 .
Teorema. A transformação conforme definida pelo versor V é uma isometria se, e somente se,

Ve ∞ V -1 = e ∞ .
Usando o teorema acima em conjunto com as definições da Figura 8 temos o seguinte resultado:

Proposição. Uma transformação conforme é uma isometria se, e somente se, é uma composição de translação, rotação e reflexão.

A demonstração destes resultados segue de expandir as definições envolvidas e testar todos casos possíveis. Detalhes podem ser encontrados em [START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for computer vision and graphics[END_REF].

Com respeito ao MDGP, os resultados acima são de especial interesse, pois buscamos determinar a conformação molecular a menos de rotação e translação. As ferramentas aqui vistas da AGC são adequadas para obtermos uma solução que tenha essas características.

Versores com o CLUCalc. Uma conhecida implementação da AGC em espaços 3D é o

CLUCalc [START_REF] Perwass | CLUCalc v4.3.2[END_REF]. Ele possui uma versão do rotor (2.26), de forma que podemos realizar a rotação de objetos 3D utilizando a AGC. Por exemplo, para rotacionarmos o ponto P = e 3 do R 3 Na figura acima temos a rotação, via rotor (2.30), do círculo κ, plano π e esfera σ, definidos conforme a Figura 7. Isso mostra o potencial de generalização da AGC ao tratar todos objetos geométricos como vetores. Essa característica fornece vantagens quando lidamos com o problema da interseção de esferas, pois não precisamos interpretar as esferas como um conjunto de pontos, mas sim como um único objeto matemático. Dessa maneira, para realizar a interseção entre esferas estaremos operando as esferas como se fossem vetores no espaço conforme, e não como se fossem conjuntos de pontos do espaço Euclideano.

P conf = RP conf R -1 .

Esferas como vetores tangentes

Uma forma alternativa de representar em R n+1,1 uma esfera de centro c e raio r é através de um ponto p na esfera e seu centro c4 . Tal representação é dada por

σ = p • c ∧ e ∞ .
(2.31)

Aqui c ∧ e ∞ denota o ponto flat determinado pelo centro da esfera, i.e., a interseção de uma reta passando pelo centro da esfera com um plano que contém este centro. De fato, (2.31) é a representação dual de uma esfera, pois 

σ = p • (c ∧ e ∞ = (p • c)e ∞ -(p • e ∞ )c = - 1 2 ||p -c|| 2 + c
σ = c - r 2 2 e ∞ ,
que é a representação dual da esfera assim como (2.21).

O par de pontos

No modelo conforme o par de pontos é um objeto primitivo, i.e., pode ser manipulado como um vetor do espaço vetorial R n+1,1 . Em [START_REF] Dorst | Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[END_REF] é usado o termo em inglês round tanto para esferas como para círculos ou par de pontos. Em [START_REF] Fernandes | Álgebra Geométrica e Aplicações[END_REF] este aspecto é apresentado na seção sobre blades vistos como circunferências. É importante notar que no modelo conforme as circunferências englobam as esferas, círculos e par de pontos, possibilitando uma unificação na forma de lidar com estes objetos geométricos. De fato, o que distingue tais objetos na AGC é o raio, o centro e o espaço subjacente usado na definição de cada um destes. Dessa maneira, os blades vistos como circunferências, ou rounds, são definidos e manipulados algebricamente da mesma maneira.

Um par de pontos no R 3 , i.e., uma 1-esfera, tem representação primal dada por 1 . Usaremos a notação p p para representação dual do par de pontos, i.e., p p = P * p . Podemos obter a representação dual de um par de pontos através de

P p = p 1 ∧ p 2 , onde p 1 , p 2 são pontos em R n+1,
p p = σ 1 ∧ σ 2 ∧ σ 3 , (2.32)
onde σ i denota a esfera dual definida por (2.21), para i = 1, 2, 3. Assumindo que estas esferas são distintas, então a interseção descrita em (2.32) resulta na representação dual de um par de pontos, i.e., em uma 1-esfera.

Além da possibilidade de representar objetos geométricos de forma compacta, uma das vantagens da AGC é permitir manipulá-los algebricamente de uma maneira mais simples, se comparado com a abordagem clássica via álgebra linear. Por exemplo, sob certas condições, o resultado da interseção de n esferas {σ i } n i=1 em R n+1,1 pode ser obtido computando o produto exterior entre tais esferas, e o resultado é um par de pontos dual

p p = σ 1 ∧ • • • ∧ σ n .
(2.33)

No Capítulo 4 temos a demonstração deste resultado e de (2.32).

A seguinte fórmula extrai os pontos de um par de pontos,

p 1,2 = ∓p - * p ± p - * p • p - * p e ∞ • p - * p = ∓P p ± P p • P p e ∞ • P p , ( 2.34) 
onde p p é dado por (2.33) e σ i é a representação dual da esfera i em R n+1,1 , assim como anteriormente. Notemos que, como

p p = P * p = (σ 1 ∧ • • • ∧ σ n ) * = (p 1 ∧ p 2 ) * ,
onde p 1 e p 2 são os pontos resultantes de (2.33), então,

p - * p = (σ 1 ∧ • • • ∧ σ n ) - * = P p = p 1 ∧ p 2 .
Demonstração da fórmula para extrair os pontos de um par de pontos. Deseja 

p - * p • p - * p = (p 1 ∧ p 2 ) 2 = p 1 • p 2 . (2.35)
Usando as propriedades do produto geométrico, temos que

p 1 ∧ p 2 2 = 1 2 p 1 p 2 -p 2 p 1 2 = 1 4 p 1 p 2 p 1 p 2 -p 1 p 2 2 p 1 -p 2 p 2 1 p 2 + p 2 p 1 p 2 p 1 = 1 4 p 1 p 2 p 1 p 2 + p 2 p 1 p 2 p 1 = 1 4 p 1 p 2 p 1 p 2 + p 2 p 1 p 2 p 1 = 1 4 p 1 • p 2 p 1 p 2 + p 1 ∧ p 2 p 1 p 2 + p 2 p 1 p 2 • p 1 + p 2 p 1 p 2 ∧ p 1 = 1 4 2p 1 • p 2 p 1 p 2 + p 1 ∧ p 2 p 1 p 2 -p 1 ∧ p 2 p 1 p 2 = 1 4 2p 1 • p 2 p 1 p 2 = 1 2 p 1 • p 2 p 1 p 2 , onde p 2 p 1 p 2 = p 2 (p 1 p 2 ) = p 2 p 1 • p 2 + p 1 ∧ p 2 = p 2 p 1 • p 2 + p 2 p 1 ∧ p 2 = p 2 p 1 • p 2 + p 2 • p 1 ∧ p 2 + p 2 ∧ p 1 ∧ p 2 = p 2 p 1 • p 2 + p 2 • p 1 p 2 -p 2 • p 2 p 1 = p 2 p 1 • p 2 + p 2 • p 1 p 2 = 2 p 1 • p 2 p 2 .
Logo,

p 1 ∧ p 2 2 = p 1 • p 1 • p 2 p 2 = (p 1 • p 2 p 1 • p 2 = p 1 • p 2 2 , mostrando (2.35).
Notemos que

e ∞ • p - * p = e ∞ • p 1 ∧ p 2 = e ∞ • p 1 p 2 -e ∞ • p 2 p 1 = e ∞ • e 0 p 2 -e ∞ • e 0 p 1 = p 1 -p 2 .
Então, usando a definição de inversa (2.18), obtemos

1 p 1 -p 2 = p 1 -p 2 p 1 -p 2 2 .
Como 

p 1 -p 2 2 = p 1 -p 2 p 1 -p 2 = p 2 1 -p 1 p 2 -p 2 p 1 + p 2 2 = -p 1 p 2 + p 2 p 1 = -p 1 • p 2 + p 1 ∧ p 2 + p 2 • p 1 + p 2 ∧ p 1 = -2 p 1 • p 2 , então, 1 e ∞ • p - * p = 1 p 1 -p 2 = - p 1 -p 2 2 p 1 • p 2 = 1 2 p 2 -p 1 p 1 • p 2 . ( 2 
p - * p -p - * p • p - * p e ∞ • p - * p = 1 2 p 1 • p 2 p 2 -p 1 p 1 ∧ p 2 -p 1 • p 2 = 1 2 p 1 • p 2 p 1 -p 2 p 2 p 1 = 1 2 p 1 • p 2 p 1 p 2 p 1 -p 2 2 p 1 = 1 2 p 1 • p 2 p 1 p 2 p 1 = 1 2 p 1 • p 2 p 1 p 2 • p 1 + p 2 ∧ p 1 = 1 2 p 1 • p 2 p 2 • p 1 p 1 + p 1 p 2 ∧ p 1 = 1 2 p 1 • p 2 p 1 • p 2 p 1 + p 1 • p 2 ∧ p 1 + p 1 ∧ p 2 ∧ p 1 = 1 2 p 1 • p 2 p 1 • p 2 p 1 + p 1 • p 2 )p 1 -p 1 • p 1 p 2 = 1 2 p 1 • p 2 p 1 • p 2 p 1 + p 1 • p 2 )p 1 = p 1 , que é o resultado procurado. De forma análoga, obtemos p 2 , -p - * p + p - * p • p - * p e ∞ • p - * p = p 2 .

Interseção e união com a AGC

Vimos que na AGC os subespaços são representados por blades. Além disso, os blades possuem informações como orientação e magnitude do subespaço que codifica. Já mencionamos que, para realizar a interseção e a união de subespaços, é importante conhecermos a orientação relativa entre os subespaços envolvidos. A AGC possui duas operações, conhecidas como join e meet, que permitem realizarmos a interseção e união de subespaços de forma eficiente. De fato, estas operações são produtos através dos quais podemos obter as conhecidas operações de interseção e união de subespaços, tanto para os casos comuns, como para casos particulares. Por exemplo, é possível realizarmos a interseção de uma reta contida em um plano, obtendo uma reta como resultado; ou a interseção de uma reta não paralela a um plano, resultando em um ponto. Isto exemplifica casos em que a interseção entre objetos 2D e 1D pode ser tanto objetos 1D como 0D, i.e., escalares. A seguir mostraremos como tal característica da interseção é contemplada pela operação meet. Através do meet podemos determinar sem ambiguidades o subespaço resultante da interseção. (2.37)

Construção do meet

Como A e B são blades, estes podem ser fatorados através do produto exterior de forma que

A = A ∧ M, B = M ∧ B ,
onde A e B são as partes de A e B, respectivamente, que não contém M . Sendo assim, podemos escrever (2.37) como

J = A ∧ M ∧ B .
Como A e B não contém M , podemos escolher uma base para A e B tal que todos seus elementos sejam ortogonais a M . Consequentemente, sob esta base, os elementos de A e B são ortogonais a M -1 . Com isso, usando as contrações via produto interno (2.4), obtemos

A = A M = A M -1 = (A ∧ M ) M -1 ,
(2.38)

B = M B = M -1 B = M -1 (M ∧ B ). (2.39) 
As identidades acima eliminam ambiguidades que poderiam aparacer caso reescalemos o blade M , digamos por um fator µ. Isto é, se multiplicamos M por µ, então, pela definição de blade, aparece um fator 1/µ reescalando seu inverso M -1 . Ou seja, para todo µ ∈ R não nulo, temos

M -→ µM =⇒ M -1 -→ 1 µ M -1 .
Na definição de meet e join desejamos que os blades M e J obtidos sejam invariantes sob reescalamento. Para evitar esta ambiguidade usaremos as identidades (2.38) e (2.39).

Já que ambas expressões envolvem tanto M como M -1 , os fatores µ e 1 µ de possíveis reescalamentos se compensam. Assim, ambas expressões, e também as demais aqui obtidas para join e meet , são invariantes sob reescalamento. Além disso, através de tais identidades podemos escrever o join como Assim como definimos o meet para obter a interseção entre dois subespaços, através de relações de dualidade é possível realizarmos a interseção através do join. No Capítulo 4, veremos como isso se dá. Aqui optamos por construir o join e meet seguindo a maneira usual da literatura na área, pois esta permite uma interpretação natural das operações realizadas entre os subespaços. De forma geral, dualizando temos que

J = A ∧ B = A ∧ (M -1 B) ou J = A ∧ B = (A M -1 ) ∧ B. (2.40) Usando a identidade 1 = J • J -1 , ficamos com M = (B J -1 ) A. ( 2 
M * = A ∩ B * = B * ∧ A * ,
onde a dualização de A e B são com respeito ao join, i.e., A * = AJ -1 e B * = BJ -1 . Isso mostra que, de posse da representação dual de objetos no espaço conforme, a interseção pode se reduzir ao produto exterior, o que é análogo a definição de join apresentada inicialmente. 

Exemplo da não

O problema na abordagem clássica

Na abordagem clássica [START_REF] Coope | Reliable computation of the points of intersection of n spheres in R n[END_REF][START_REF] Maioli | Interseção de Esferas no R n e Aplicações[END_REF][START_REF] Mucherino | Distance Geometry: Theory, Methods, and Applications[END_REF] usamos ferramentas da álgebra linear e de análise de matrizes [START_REF] Watkins | Fundamentals of Matrix Computations[END_REF][START_REF] Meyer | Matrix Analysis and Applied Linear Algebra[END_REF][START_REF] Shilov | Linear Algebra[END_REF] para obter o resultado da interseção entre esferas no R n . Em tal abordagem, ao invés de resolver o sistema não-linear (1.1) de forma direta, obtemos um problema equivalente que é linear. Neste capítulo veremos como se dá o processo de linearização para diferentes configurações dos centros das esferas a serem intersectadas. O efeito de se acrescentar uma casca esférica ao problema também é apresentado [START_REF] Maioli | Interseção de Esferas no R n e Aplicações[END_REF]. 

||x|| 2 -2x t a i + ||a i || 2 = d 2 i .
A expressão acima pode ser escrita de forma compacta como

a t i x = r + b i 2 , com r = ||x|| 2 e b i = ||a i || 2 -d 2 i , para i = 1, . . . , n. Ou ainda, A t x = re + b 2 , ( 3.2 
)

onde e = [1 . . . 1], b = [b 1 . . . b n ] e A t denota a transposta da matriz A. Como a matriz A é não-singular, A t é não-singular com inversa A -t . Logo, por (3.2), obtemos x = 1 2 ru + v , ( 3.3) 
sendo u = A -t e e v = A -t b, i.e., u e v são soluções (únicas) de

       A t u = e, A t v = b. (3.4) 
Usando a definição de r e (3.3), temos que

4r = 4x t x = ru + v t ru + v .
Ou seja, r satisfaz

u t u r 2 + (2u t v -4) r + v t v = 0,
que é uma equação quadrática em r com raízes dadas por

r = 2 -u t v ± √ ∆ u t u , (3.5) onde ∆ = (2 -u t v) 2 -u t u v t v.
Portanto, por (3.5), concluímos que: (i) se ∆ < 0, então a solução real é vazia; (ii) se ∆ ≥ 0, então os pontos da interseção são obtidos computando (3.5) e substituindo em (3.3), i.e.,

x = 1 2   2 -u t v ± √ ∆ u t u + v   .
Computacionalmente, os valores de u e v em (3.4) são obtidos através da fatoração LU em A t e usando a definição (3.3). Logo, o custo computacional desse método é O(n 3 ).

Segundo método -centros A.I.

Consideremos n esferas S i (a i , d i ) no R n de raios d i , cujos centros a i são A.I., onde i = 1, . . . , n. Já que nem todo conjunto A.I. é L.I., esse caso generaliza o do primeiro método. De fato, uma maneira de obter um conjunto A.I. a partir de um L.I. é realizando uma translação do segundo. A recíproca também é válida. Logo, o conjunto {a 1 -a n , . . . , a n-1 -a n }, obtido através da translação por -a n do conjunto dos n centros a i , é L.I. e a matriz n × (n -1)

Ā = a 1 -a n , . . . , a n-1 -a n ,
possui n -1 colunas L.I. Isto implica em Ā ter posto completo, i.e., posto( Ā) = n -1. Dessa maneira, se x ∈ R n satisfaz (3.1) e os centros a i são A.I., após a translação de x dada por x = xa n , os pontos na solução são tais que

||x -(a i -a n )|| 2 = d 2 i , ( 3.6) 
para i = 1, . . . , n. Em particular, quando i = n, obtemos

||x|| 2 = d 2 n . (3.7) Expandindo (3.6), para i = n, temos que ||x|| 2 -2x t (a i -a n ) + ||a i -a n || 2 = d 2 i .
Então, por (3.7), reescrevemos a expressão acima como

d 2 n -2x t (a i -a n ) + ||a i -a n || 2 = d 2 i .
Ou ainda, por

(a i -a n ) t x = - 1 2 d 2 i -d 2 n -||a i -a n || 2 , onde i = 1, . . . , n -1. Logo, a expressão acima na forma matricial é dada por Āt x = c, (3.8 
)

onde c = [c 1 . . . c n-1 ], c i = - 1 2 d 2 i -d 2 n -||a i -a n || 2 e i = 1, . . . , n -1.
Como este sistema é subdeterminado e de posto completo, então possui infinitas soluções. No entanto, buscamos soluções de (3.8) que também sejam soluções de (3.6). Para isso consideramos a decomposição QR de Ā,

Ā = QR = Q   R 0   , ( 3.9) 
onde Q é uma matriz ortogonal n × n e R é uma matriz (n -1) × (n -1) não-singular e triangular superior. Assim, substituindo (3.9) em (3.8), obtemos

R t Q t x = c,
o que equivale a resolvermos

R t w = c, (3.10) 
e, em seguida, Como Rt é não-singular o sistema acima tem solução única. Agora precisamos encontrar os valores de z em (3.12).

Q t x = w. ( 3 
Já que

Q t = Q -1
, usando a definição de x e w em (3.11), obtemos

x = x + a n = Qw + a n = Q   y z   + a n , (3.13)
onde w é dado por (3.12). Já que x é tal que

||x -a i || 2 = d 2 i , para i = 1, . . . , n, em particular, temos Q   y z   + a n -a n 2 = d 2 n , quando i = n. Logo,   y z   2 = d 2 n ,
pois Q é ortogonal e, consequentemente, preserva a norma-2. Com isso, obtemos

z = ± √ δ, (3.14) com δ = d 2 n -||y|| 2 .
Portanto, concluímos que: (i) se δ < 0, a solução é vazia; (ii) se δ = 0, então x é dado por (3.13) com z = 0; e (iii) se δ > 0, então obtemos dois valores de z por (3.14) e as respectivas soluções x por (3.13).

Terceiro método -caso geral

Consideremos m esferas S i (a i , d i ) no R n de raios d i e centros a i ∈ R n , onde i = 1, . . . , m. Nos dois métodos anteriores, a interseção entre as esferas foi uma das três possibilidades: (i) vazia; (ii) um ponto; ou (iii) dois pontos. Agora, além destas possibilidades, a interseção também pode ser uma (n -k)-esfera. 

Após transladarmos os m centros

A = {a 1 , . . . , a m } por -a m , obtemos o conjunto {a 1 -a m , . . . , a m-1 -a m , 0} e definimos Ā = {a 1 -a m , . . . , a m-1 -a m }. O invólucro afim de A tem dimensão k, onde 1 ≤ k ≤ min{m -1, n}.
||x|| 2 -2x t (a i -a m ) + ||a i -a m || 2 = d 2 i .
Então, usando (3.16), reescrevemos a expressão acima como

(a i -a m ) t x = - 1 2 d 2 i -d 2 m -||a i -a m || 2 , onde i = 1, . . . , m -1. Ou ainda, na forma matricial, Āt x = c, (3.17 
) 1 , supomos que as k primeiras colunas de Ā são L.I. Dessa maneira, a decomposição QR de Ā é dada por

onde c = [c 1 . . . c m-1 ] e c i = - 1 2 d 2 i -d 2 m -||a i -a m || 2 , sendo i = 1, . . . , m -1. Como posto( Ā) = k, s.p.g.
Ā = QR = Q   R 0   , (3.18) onde Q é uma matriz ortogonal n × n e R é uma matriz k × (m -1) de posto completo.
Logo, usando a decomposição (3.18) em (3.17), ficamos com

R t Q t x = c.
O problema acima equivale a resolvermos

R t w = c, (3.19) 
e 

Q t x = w. (3.20) Seja w =   y z   , onde y ∈ R k e z ∈ R n-k . Então, ( 3 
a i || 2 = d 2 i , onde i = 1, . . . , m, então, para i = m, temos Q   y z   + a m -a m 2 = d 2 m .
Logo,

  y z   2 = d 2 m , ( 3.23) 
pois Q é ortogonal e preserva a norma-2. Notemos que (3.23) é a equação de uma n-esfera no R n , com centro na origem e raio d m . Expandindo (3.23), obtemos

||y|| 2 + ||z|| 2 = d 2 m .
Dessa maneira, 

z 2 1 + • • • + z 2 n-k = ρ 2 , ( 3 
Ā = QR = Q R 0 = Q R1 R2 0 0 , onde Q é uma matriz n × n ortogonal, R 1 é uma matriz k × k não-singular e triangular superior e R2 é uma matriz k × (m -1 -k). Como R = [ R1 R2 ], então podemos reescrever (3.21) como Rt 1 Rt 2 y = c 1 c 2 , onde [c 1 c 2 ] = c, c 1 ∈ R k e c 2 ∈ R n-k . Logo, y será solução se satisfizer o sistema    Rt 1 y = c 1 , Rt 2 y = c 2 .
De forma equivalente, como Rt 1 é não-singular, da primeira equação do sistema acima, temos que y = R-t

1 c 1 será solução de (3.21) se satisfizer a condição de || Rt 2 yc 2 || = 0. Neste caso, tal y é único e pertence a imagem de Rt . z = 0 e x é dado por (3.22); ou (iii) se ρ 2 > 0, obtemos os valores de z por (3.24) e os respectivos pontos x na interseção por (3.22). Notemos que, no caso (iii), como y ∈ R k , temos a interseção das m esferas com um subespaço de dimensão k, o que resulta em uma (n -k)-esfera do R n .

Observação. Em particular, quando m = n, então k = n -1, de forma que (iii) se reduz a um par de pontos. De fato, neste caso temos a interseção de n esferas no R n cujos centros são A.I., e o problema se reduz ao segundo método visto anteriormente.

Interseção de esferas e uma casca esférica

Consideremos m esferas S i (a i , d i ) no R n de raios d i e centros a i ∈ R n , sendo i = 1, . . . , m, e uma casca esférica S m+1 (a m+1 , d m+1 , d m+1 ) de centro a m+1 ∈ R n e raios d m+1 , d m+1 tais que d m+1 > d m+1 . Como antes, denotemos por k a dimensão de aff(A), onde A = {a 1 , . . . , a m } e 1 ≤ k ≤ min{m -1, n}. Procuramos x ∈ R n tal que        ||x -a i || 2 = d 2 i , i = 1, . . . , m, d 2 m+1 ≤ ||x -a m+1 || 2 ≤ d 2 m+1 .
(

Baseado na ideia apresentada no terceiro método visto acima, queremos mostrar que a interseção entre as esferas e a casca esférica pode ser: (i) vazia; (ii) um ponto; (iii) uma (n -k)-esfera; ou (iv) a união de (n -k -1)-esferas. 

       ||x -(a i -a m )|| 2 = d 2 i , i = 1, . . . , m, d 2 m+1 ≤ ||x -(a m+1 -a m )|| 2 ≤ d 2 m+1 .
(3.27)

Logo, para i = m,

||x|| 2 = d 2 m . (3.28)
Já para i = m, por (3.27), obtemos

       ||x|| 2 -2x t (a i -a m ) + ||a i -a m || 2 = d 2 i , i = 1, . . . , m -1, d 2 m+1 ≤ ||x|| 2 -2x t (a m+1 -a m ) + ||a m+1 -a m || 2 ≤ d 2 m+1 .
Usando (3.28), o sistema acima assume a seguinte forma:

       (a i -a m ) t x = - 1 2 d 2 i -d 2 m -||a i -a m || 2 , i = 1, . . . , m -1, - 1 2 d 2 m+1 -d 2 m -||a m+1 -a m || 2 ≤ (a m+1 -a m ) t x ≤ - 1 2 d 2 m+1 -d 2 m -||a m+1 -a m || 2 .
Ou ainda,

       āt i x = c i , i = 1, . . . , m -1, c m+1 ≤ āt m x ≤ c m+1 , (3.29) 
onde

c i = - 1 2 d 2 i -d 2 m -||a i -a m || 2 , c m+1 = - 1 2 d 2 m+1 -d 2 m -||a m+1 -a m || 2 , c m+1 = - 1 2 d 2 m+1 -d 2 m -||a m+1 -a m || 2 e
āi é a coluna i da matriz Ā, definida em (3.26).

Computando a decomposição QR de ĀE, temos que

ĀE = QR = Q   R 1 r k+1 R 2 0 0 0   = Q      R1 rk+1 R2 0 rk+1,k+1 0 0 0 0      , ( 3.30) 
onde as matrizes acima são tais que

Q é n × n e ortogonal; R 1 = [ Rt 1 0] t é (k + 1) × k, com R1 sendo k × k triangular superior de posto completo; r k+1 = [r k+1 rk+1,k+1 ] t ∈ R k+1 , onde rk+1 ∈ R k e rk+1,k+1 ∈ R; R 2 = [ Rt 2 0] é (k + 1) × (m -k -1) e R2 é k × (m -k -1
). Todas essas matrizes são determinadas usando as partições obtidas pela decomposição QR de ĀE. A última igualdade do lado direito em (3.30) vem do fato de que as colunas k + 2 a m de ĀE são combinações lineares das k primeiras colunas, não dependendo da coluna k + 1. Tal característica dos centros das esferas e da casca esférica fornece essa forma especial para a decomposição QR, de forma que a última linha da matriz R 2 seja nula, conforme vemos em (3.30).

Como E t = E -1 , então ( ĀE) t = (QR) t =⇒ E t Āt = R t Q t =⇒ Āt = ER t Q t . Logo, pela decomposição (3.30), Āt x = ER t Q t x = E      Rt 1 0 0 rt k+1 rk+1,k+1 0 Rt 2 0 0      Q t x =      Rt 1 0 0 Rt 2 0 0 rt k+1 rk+1,k+1 0      Q t x. (3.31)
Usando a seguinte definição,

Q t x = w =      y y k+1 z      , (3.32) onde y ∈ R k , y k+1 ∈ R e z ∈ R n-k-1 , o sistema (3.31) se reduz a Āt x =   Rt 0 rt k+1 rk+1,k+1     y y k+1   + 0 t z, onde R = [ R1 R2 ].
Em vista disso, (3.29) pode ser escrito como 

           Rt y = c, c m+1 ≤ rt k+1 rk+1,k+1   y y k+1   ≤ c m+1 . ( 3 
a i || 2 = d 2 i , onde i = 1, . . . , m. Logo, para i = m, Q      y y k+1 z      + a m -a m 2 = d 2 m .
Usando a ortogonalidade de Q,

     y y k+1 z      2 = d 2 m .
Dessa maneira, pela definição de norma-2, podemos escrever a expressão acima como

||y|| 2 + y 2 k+1 + ||z|| 2 = d 2 m .
Portanto, Ou seja,

||z|| 2 = d 2 m -||y|| 2 -y 2 k+1 . ( 3 
z 2 1 + • • • + z 2 n-k = ρ 2 , onde ρ 2 = d 2 m -||y|| 2 .
Portanto, o resultado da interseção depende de ρ 2 , sendo: (i) vazia, se ρ 2 < 0; (ii) um ponto, se ρ 2 = 0; ou (iii) uma (n -k)-esfera, se ρ 2 > 0.

O problema usando a AGC

Nesta capítulo veremos como realizar a interseção de esferas no R n construindo uma abordagem que estende a já conhecida na literatura de álgebra geométrica conforme (AGC) [START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for computer vision and graphics[END_REF][START_REF] Dorst | Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[END_REF][START_REF] Fernandes | Álgebra Geométrica e Aplicações[END_REF][START_REF] Perwass | Geometric algebra with applications in engineering[END_REF][START_REF] Hildenbrand | Foundations of Geometric Algebra Computing[END_REF]. Assumiremos que as esferas são distintas, i.e., nenhuma delas possui, ao mesmo tempo, raios e centros iguais entre si. (-1)

1 2 (k-1)(k-2) , pois grau(σ) = k e grau(e ∞ • σ) = k -1. Logo, sgn(r 2 ) = (-1) 1+k (-1) -1 2 (k-1)(k-2) = (-1) -k 2 2 + 5k 2 = (-1) 1 2 k(1-k) = sgn(σ • σ), ( 4.2) 
sendo sgn( σ) dado de acordo com (2.16). Notemos que, quando σ for um ponto, usando (4.1), obtemos t = 0.

Ao longo deste capítulo vamos analisar o sinal de t (4.1) para determinarmos o resultado obtido da interseção entre as esferas.

Esferas com centros L.I.

Consideremos n esferas S i (a i , d i ) no R n de raios d i , cujos centros a i ∈ R n são L.I., sendo i = 1, . . . , n. Representemos essas n esferas em R n+1,1 por

σ i = a i - d 2 i 2 e ∞ , ( 4.3) 
onde

a i = e 0 + a i + ||a i || 2 2 e ∞ , para i = 1, . . . , n.
Um caso particular. Antes de obtermos a interseção para o caso geral nD, vejamos o caso em que n = 3. A interseção de duas esferas σ 1 e σ 2 , definidas por (4.3), é dada por

κ = σ 1 ∧ σ 2 .
Para qualquer p ∈ R 4,1 , temos que

0 = p • κ = p • σ 1 ∧ σ 2 = p • σ 1 σ 2 -p • σ 2 σ 1 . (4.4)
Como os centros {a i } n i=1 são L.I., então as esferas {σ i } n i=1 são L.I. Logo, os coeficientes de (4.4) são nulos, i.e.,

       p • σ 1 = 0, p • σ 2 = 0.
Usando o mesmo procedimento feito para obter (2.22), reescrevemos o sistema acima como

||x -a i || 2 = d 2 i , ( 4.5) 
onde i = 1, 2. Isto equivale ao conjunto dos pontos x ∈ R 3 pertencentes a ambas esferas, ou seja, que definem um círculo no R 3 . Prosseguindo, realizamos a interseção do círculo κ com a esfera σ 3 através do produto exterior:

p p = κ ∧ σ 3 .
O resultado p p é um par de pontos, pois de

0 = p • p p = p • κ ∧ σ 3 = p • κ σ 3 -p • σ 3 κ, e, para todo p ∈ R 4,1 , temos que        p • κ = 0, p • σ 3 = 0. Ou ainda, ||x -a i || 2 = d 2 i , ( 4.6) 
para i = 1, 2, 3. Como o sistema acima representa a interseção de três esferas do R 3 cujos centros são L.I., então o resultado da solução é um par de pontos no R 3 .

De posse do par de pontos na forma dual, dado por

p p = σ 1 ∧ σ 2 ∧ σ 3 ,
e com auxílio da fórmula (2.34), podemos obter os pontos do resultado da interseção entre três esferas de forma explícita.

Caso geral. Agora vamos mostrar que a interseção das n esferas

S i (a i , d i ) no R n é dada por σ = σ 1 ∧ • • • ∧ σ n , ( 4.7) 
onde cada σ i é definida por (4.3). De fato, dado um ponto p ∈ R n+1,1 , temos que Quando a solução são os dois pontos, i.e., é dada por (iii), podemos obtê-los explicitamente através da fórmula (2.34), sendo que no lugar de p p , usamos σ fornecido por (4.7). No caso da solução ser um ponto, (2.34) fornecerá dois pontos iguais.

0 = p • σ 1 ∧ • • • ∧ σ n = p • σ 1 ∧ σ 2 ∧ • • • ∧ σ n -σ 1 ∧ p • σ 2 ∧ • • • ∧ σ n + . . . • • • -(-1) n σ 1 ∧ σ 2 ∧ • • • ∧ p • σ n . Como {σ i } n i=1 é L.I.,

Esferas com centros A.I.

Consideremos n esferas S i (a i , d i ) no R n de raios d i e cujos centros a i ∈ R n são A.I., para i = 1, . . . , n. A representação dual dessas n esferas em R n+1,1 é definida por

σ i = a i - d 2 i 2 e ∞ , onde a i = e 0 + a i + ||a i || 2 2 e ∞ , para i = 1, . . . , n.
Como {a i } n i=1 é A.I., então {a i } n i=1 é L.I., implicando em {σ i } n i=1 ser L.I. Logo, podemos realizar a interseção entre as n esferas utilizando o produto exterior, assim como fizemos anteriormente. Dessa maneira, a interseção das n esferas no R n é dada por

σ = σ 1 ∧ • • • ∧ σ n . (4.10)
Portanto, tendo obtido (4.10), definimos t = σ • σ tal que a interseção das n esferas no R n é uma das possibilidades: (i) vazia, se t < 0; (ii) um ponto, se t = 0; ou (iii) dois pontos, se t > 0.

Novamente, podemos extrair os pontos da solução através da fórmula (2.34), usando σ obtido em (4.10) no lugar de p p .

Observação. Analisar o sinal de t é mais simples do que analisar o raio da esfera, visto que não precisamos obter este raio explicitamente.

Destacamos que, embora a literatura de AGC trate do problema de interseção de esferas para casos de centros L.I. e A.I., em espaços 3D desconhecemos uma apresentação rigorosa para casos nD.

Esferas com centros quaisquer

Consideremos m esferas S i (a i , d i ) no R n com raios d i e centros a i ∈ R n , para i = 1, . . . , m. A representação dual dessas m esferas em R n+1,1 é dada por σ i = a i - d 2 i 2 e ∞ , onde a i = e 0 + a i + ||a i || 2 2
e ∞ e i = 1, . . . , m. Como no terceiro método da abordagem clássica, transladando os centros {a i } m i=1 por -a m , obtemos Ā = {ā i } m i=1 , onde definimos āi = a i -a m , para i = 1, . . . , m. Vimos que dim(aff({a i } m i=1 )) = k e, assim como antes, 1 ≤ k ≤ min{m -1, n}. Além disso, podemos supor, s.p.g. 

= p • σ = p • σ1 ∧ • • • ∧ σk = p • σ1 ∧ σ2 ∧ • • • ∧ σk -σ1 ∧ p • σ2 ∧ • • • ∧ σk + . . . • • • -(-1) k σ1 ∧ σ2 ∧ • • • ∧ p • σk .
Como {σ i } k i=1 é L.I., da expressão acima, temos que p • σi = 0, (4.12)

1 Sem perda de generalidade. Por fim, realizamos a interseção das m -k esferas restantes com a (n -k)-esfera σ já obtida em (4.11).

Usando o join para interseção. Como as m -k esferas restantes não são L.I. nem A.I., para realizarmos a interseção entre estas e σ (4.11), a princípio, devemos utilizar a operação de join, através da dualização de (2.41). Dessa maneira, a interseção é dada por Interseção das m -k esferas restantes sem o join. Como o resultado da interseção das k primeiras esferas transladadas é a (n -k)-esfera (4.11), então quando realizarmos a interseção com a próxima esfera, estaremos realizando a interseção entre o k-blade σ e o 1-blade σk+1 . Logo, temos duas possibilidades para a interseção: ou σk+1 pertence a σ, ou não pertence. Supondo que a interseção é não vazia, no primeiro caso, a interseção entre σ e σk+1 continua sendo σ. Já no segundo caso, a interseção é uma (n -k -1)-esfera. Assim, realizamos a interseção do resultado obtido com a esfera σk+2 , que é um 1-blade. Ou seja, temos duas possibilidades para a interseção envolvendo σk+2 , conforme a análise feita quando acrescentamos σk+1 . Analisando desta maneira, continuamos o procedimento acrescentando as m -k esferas restantes, até finalizarmos com a esfera σm . Escrevemos este processo por Portanto, após obter σ (4.14), definimos t = σ • σ, e temos as seguintes possibilidades para a interseção das m esferas no R n : (i) vazia, se t < 0; (ii) um ponto, se t = 0; ou (iii) uma (n -k)-esfera, se t > 0.

σ = σ1 ∧ • • • ∧ σk ∧ ∧ ∧ σk+1 . . . ∧ ∧ ∧ σm ,
σ(r+1) =        σ(r) , se σ(r) ∧ σr+1 = 0, σ(r) ∧ σr+1 , se σ(r) ∧ σr+1 = 0,
Observações. A operação de join é não-linear, de forma que sua implementação computacional é dificultada. Em [START_REF] Fontijne | Efficient implementation of geometric algebra[END_REF], há um algoritmo O(n 2 ) para o join. A não linearidade do join está associada ao pseudoescalar do espaço determinado pela interseção (ou união) dos subespaços em que estamos realizando a operação, visto que a cada etapa da interseção entre m esferas, o pseudoescalar da interseção pode mudar. No caso de sabermos a priori o pseudoescalar das etapas, o join se torna linear. Na fórmula recursiva (4.13), exploramos o fato de estarmos realizando interseção exclusivamente entre esferas. Com isso foi possível encontrarmos uma forma de obter a interseção evitando o uso do join. Esta particularidade permitiu que a interseção entre esferas fosse realizada basicamente através do produto exterior em todos os casos, resultado que estende os já conhecidos na literatura de AGC. 

Interseção de esferas e uma casca esférica via AGC

Consideremos m esferas S i (a i , d i ) no R n com raios d i e centros a i ∈ R n , para i = 1, . . . , m e uma casca esférica S m+1 de centro a m+1 ∈ R n e raios d m+1 , d m+1 tais que

d m+1 > d m+1 . Seja dim(aff(A)) = k, onde A = {a 1 , . . . , a m } e 1 ≤ k ≤ min{m -1, n}. Procuramos x ∈ R n tal que        ||x -a i || 2 = d 2 i , i = 1, . . . , m, d 2 m+1 ≤ ||x -a m+1 || 2 ≤ d 2 m+1 . (4.15)
Usando a AGC, queremos mostrar que a interseção entre as esferas {S i } m i=1 e a casca esférica S m+1 pode ser: (i) vazia; (ii) um ponto; (iii) uma (n -k)-esfera; ou (iv) a união de (n -k -1)-esferas. Consideremos a seguinte representação dual em R n+1,1 para as esferas {S i } m i=1 , 

σ i = a i - d 2 i 2 e ∞ , ( 4 
p p 2 = κ ∧ σ 3 . (4.19)
Consideremos a casca esférica S 3 representada na forma dual por

σ d = a 3 - d 2 2 e ∞ , (4.20) onde d ∈ [d 3 , d 3 ] e a 3 = e 0 + a 3 + ||a 3 || 2 2 e ∞ ∈ R 4,1 . Logo, para cada d ∈ [d 3 , d 3 ], p p d = κ ∧ σ d = σ 1 ∧ σ 2 ∧ σ d ,
é a representação dual de um par de pontos. Através de (4.18), obtemos

p p d d=d 3 = σ 1 ∧ σ 2 ∧ σ d d=d 3 = σ 1 ∧ σ 2 ∧ σ 3 = p p 1 .
De forma análoga, usando (4. [START_REF] Aragón-Camarasa | Clifford Algebra with Mathematica[END_REF],

p p d d=d 3 = p p 2 .
Portanto, a interseção do círculo (4.17) com a casca esférica (4.20) é dada por Usando a parametrização pelo raio para obter a solução no caso geral. Assim como no caso anterior em que n = 3, para o caso geral, através de (4.14), inicialmente obtemos a (n -k)-esfera σ resultante da interseção entre as m esferas no R n . Em seguida, consideramos a representação dual da casca esférica S m+1 , cujo centro foi transladado por -a m , definida por 

p p d ∈ R 4,1 : p p d = κ ∧ σ d , d ∈ [d 3 , d 3 ] . ( 4 
σ d = ām+1 - d 2 2 e ∞ , ( 4 
τ d ∈ R n+1,1 : τ d = σ ∧ σ d , d ∈ [d m+1 , d m+1 ] . ( 4 

Cenários para a interseção com uma casca esférica

A figura abaixo mostra algumas possibilidades para o resultado da interseção entre duas esferas e uma casca esférica. Casos degenerados, como esferas de raio zero, não foram considerados, pois estamos interessados em situações que tenham relação com o principal problema de aplicação, descrito no primeiro capítulo. Levando em conta esta observação, podemos desconsiderar os casos onde há pontos resultantes do tangenciamento entre cascas e esferas, visto que são pouco prováveis de ocorrerem na prática. Como, por exemplo, os casos 5, 9 e 13 da Figura 15. Aqui optamos por seguir um cenário que permita ilustrar como algumas dificuldades podem aparecer em problemas de aplicação. No caso de termos um resultado diferente de um par de arcos como a interseção entre duas esferas com uma casca esférica, quando n = 3, o procedimento para se obter a solução via AGC ainda continua sendo dado de acordo com o que já foi mostrado. 

Testes computacionais

Embora o problema de interseção de esferas seja formulado por meio de um sistema não-linear, a AGC fornece uma forma bastante eficiente de resolvê-lo. Vimos que para m esferas no R n , usando a abordagem da AGC, o problema praticamente se reduz a computar o produto exterior entre estas. Como as operações de reflexão, rotação e translação, ou composição dessas, são transformações ortogonais no espaço conforme, temos uma vantagem em relação a abordagem clássica, pois podemos inverter de maneira trivial todas operações que são realizadas ao longo das manipulações algébricas feitas na busca pela solução do problema. Vimos na Seção 2.5 alguns detalhes sobre esse aspecto.

A fim de validar essa nova abordagem, realizamos testes computacionais com o CLUCalc 4.3 [START_REF] Perwass | CLUCalc v4.3.2[END_REF] e o Wolfram Mathematica 11.2 [18] munido do pacote de álgebra de Clifford denominado clifford.m [START_REF] Aragón-Camarasa | Clifford Algebra with Mathematica[END_REF]. O CLUCalc permite um estudo bastante detalhado do espaço R Na busca de termos maior eficiência em nossos experimentos computacionais, um primeiro passo poderia ser o uso, por exemplo, de uma linguagem como o C + + para as implementações da AGC. Um aspecto a ser levado em conta nas comparações entre as abordagens é o fato de que as operações usadas na abordagem clássica são usuais em softwares como o Mathematica. Enquanto a decomposição QR de matrizes já faz parte dos pacotes internos do Mathematica, o produto geométrico, ou outras operações do modelo conforme, não faz parte. Dessa maneira, para testarmos a abordagem com a AGC, além da necessidade de termos um algoritmo que resolva nosso problema, é necessário se ter uma implementação eficiente de elementos da AGC na linguagem de programação escolhida.

Outro ponto de caráter computacional que devemos levar em conta é a existência de diferentes algoritmos para se implementar a AGC. Na maioria das vezes, as diferentes implementações exploram características específicas do problema onde se usa a AGC. Ainda não há uma implementação consolidada para o caso geral. Mais detalhes sobre esses aspectos da AGC podem ser encontrados em [START_REF] Dorst | Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[END_REF][START_REF] Perwass | Geometric algebra with applications in engineering[END_REF][START_REF] Eid | Introducing geometric algebra to geometric computing software developers: A computational thinking approach[END_REF]. Em [START_REF] Fontijne | Efficient implementation of geometric algebra[END_REF] há algoritmos eficientes que possibilitam implementarmos a abordagem aqui apresentada usando a AGC com uma complexidade computacional igual a da abordagem clássica, baseada na álgebra linear.

Comparação computacional para m = 3, . . . , 7. Seguimos [START_REF] Maioli | Interseção de Esferas no R n e Aplicações[END_REF] para gerarmos m esferas no R n cuja dimensão do invólucro afim do conjunto formado pelos centros seja k, onde 1 ≤ k ≤ min{m -1, n}. O seguinte módulo gera as esferas a serem usadas como instâncias para testarmos as abordagens vistas. Comparando os resultados da Figura 22 com a 21, notamos um aumento considerável no tempo de execução, de cerca de 2, 3 segundos para aproximadamente 13, 3 minutos. Por outro lado, o erro MDE ficou em valores baixos. Na abordagem via AGC o erro ficou da ordem de 10 -9 , enquanto na clássica o erro foi nulo. Como os métodos computacionais para trabalharmos com a AGC são assuntos de pesquisas atuais, não estando tão consolidados como os métodos para álgebra linear, consideramos que os resultados obtidos na abordagem via AGC estão adequados, pois encontrou todas as soluções do problema com uma boa precisão. De fato, utilizando implementações eficientes [START_REF] Fontijne | Efficient implementation of geometric algebra[END_REF], é possível melhorar cada vez mais a precisão das soluções encontradas pela abordagem aqui vista. Em todos testes realizados para n ≥ 15 não foi possível resolver as instâncias com o clifford.m em um tempo satisfatório.

Testes com o algoritmo BP via AGC

A fim de verificar a validade do método proposto quando lidamos com a aplicação de determinar a estrutura 3D de uma molécula de proteína, vejamos alguns experimentos levando em conta o algoritmo BP [START_REF] Liberti | A branch-and-prune algorithm for the molecular distance geometry problem[END_REF]. A versão do BP aqui utilizada foi uma adaptação do BP baseada na abordagem via AGC apresentada neste trabalho para interseção de esferas. De posse de uma implementação do BP para o Mathematica [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF], utilizamos o pacote clifford.m para construirmos a versão via AGC. A figura acima mostra os resultados obtidos para uma quantidade de átomos variando de 10 à 100, para uma instância artificial gerada no contexto do BP [START_REF] Liberti | A branch-and-prune algorithm for the molecular distance geometry problem[END_REF][START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF]. Vemos que ambas versões, tanto com a AGC quanto a clássica, mantiveram os erros MDE em valores baixos. Isso indica que a qualidade das soluções obtidas estão dentro do esperado. De fato, pelos gráficos inferimos que o BP nesta nova versão via AGC e o BP na versão clássica encontraram soluções equivalentes, visto que em ambas houve um leve aumento no erro MDE conforme aumentamos a quantidade de átomos do problema. Uma das vantagens de usarmos a AGC em conjunto com o BP é de ser possível realizarmos a interseção de esferas de forma mais natural, permitindo generalizar as etapas já presentes no BP clássico. Por exemplo, ao levarmos em conta as cascas esféricas, a etapa de interseção de esferas pode ser alterada para lidar com cascas esféricas, sendo que para tal mudança estendemos de forma natural os resultados descritos neste capítulo. O códigos acima foram as adaptações no algoritmo BP do pacote DG [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF], de forma a incluir a abordagem via AGC. Notemos que as adaptações foram tais que, em vez de usarmos a interseção de esferas na forma usual, implementamos a versão desenvolvida neste capítulo para interseção de esferas via AGC.

Testes envolvendo uma casca esférica

Vejamos alguns testes computacionais onde comparamos a abordagem clássica e a abordagem via AGC desenvolvida para o problema de interseção entre esferas e uma casca esférica, definido de acordo com (1.4).

Utilizando o módulo geraEsferas1Casca[ ] descrito na figura abaixo, obtemos instâncias com uma quantidade arbitrária de esferas e uma casca esférica, de acordo com o que vimos no Capítulo 3. Figura 25 -Implementação para gerar esferas e uma casca esférica.

Seguindo a abordagem clássica [START_REF] Maioli | Interseção de Esferas no R n e Aplicações[END_REF], implementamos o seguinte módulo para realizar a interseção entre m esferas e uma casca esférica. Testes em espaços 3D. Lembremos que a configuração principal apresentada para o problema de interseção entre duas cascas esféricas e uma casca esférica no R 3 fornece como resultado um par de arcos. Notemos que as partições envolvidas na abordagem clássica não trazem os aspectos geométricos do problema. Na Figura 29 vemos que, após utilizarmos a decomposição QR, as etapas que englobam a desigualdade de (1.4) correspondente à casca esférica S 3 não trazem nenhum caráter geométrico. Por exemplo, se quiséssemos determinar o raio, ou posição relativa entre os centros nas etapas intermediárias no processo de interseção, não saberíamos dizer olhando para as informações fornecidas pela abordagem clássica, quais valores definem o raio, ou os centros das esferas resultantes nas interseções. De fato, a Figura 29 mostra o forte apelo matricial da abordagem clássica para lidarmos com o problema. Nesse sentido, com auxílio do CLUCalc, computamos os valores envolvidos reduzindo a solução

p p d ∈ R 4,1 : p p d = κ ∧ σ d 3 , d 3 ∈ [1.5, 3.7] , (4.25) 
a seu subconjunto Observações. Enquanto a abordagem clássica forneceu um resultado cujos elementos não possuem apelo geométrico, a solução obtida via AGC forneceu a possibilidade de otimizarmos o resultado obtido, permitindo lidar com as suas particularidades de forma natural. Por exemplo, a forma compacta da solução via AGC, i.e., (4.26), fornece um conjunto solução cujos elementos descrevem de forma precisa a solução do problema. Ressaltamos que é possível recuperarmos o centro e raio das esferas obtidas em cada etapa do processo de interseção. A figura abaixo ilustra como as informações do conjunto (4.26) asseguram descrevermos de maneira precisa a região da solução cuja interseção é não vazia. De fato, a proximidade geométrica e algébrica da abordagem via AGC permite incorporamos de forma adequada em nosso modelo as particularidades presentes nos problemas de aplicação. Testes para espaços nD. Vimos para o caso 3D que a solução obtida via AGC para nosso problema tem vantagens quanto a abordagem clássica. Basta compararmos as Figuras 29 e 30. Além disso, caso consideremos esferas em espaços nD, as fórmulas do Capítulo 2 continuariam válidas e o caráter geométrico aqui explorado estaria presente. A expressão (4.24) para solução do caso nD possui a mesma forma da expressão usada para o caso 3D, i.e., de (4.21). Isso mostra que se estendermos a instância acima do caso 3D para espaços nD, podemos usar as mesmas fórmulas da AGC, pois a dimensão das esferas e casca esférica não mudariam a forma das expressões utilizadas. Por outro lado, com a abordagem clássica, as partições das matrizes envolvidas mudariam, e esta continuaria a não fornecer característica geométrica alguma do problema.

p p d ∈ R 4,1 : p p d = κ ∧ σ d 3 , d 3 ∈ [2.
Incluindo uma segunda casca esférica com a abordagem clássica. Com respeito a incluirmos uma segunda casca esférica, do ponto de vista teórico, as expressões (4.21) e (4.24) se estendem de forma natural. Basta representarmos as cascas esféricas do problema na forma dual e realizarmos a interseção por meio do produto exterior. Por exemplo, no caso de termos 5 esferas e 1 casca esférica no R 5 , sendo a dimensão do invólucro afim dos centros transladados igual a 4, basta usarmos (4.24) com κ obtido por meio de (4.13). Já para a abordagem clássica, seríamos levados a novas partições das matrizes envolvidas neste caso 5D. Vejamos abaixo os resultados de testes computacionais com a abordagem clássica feitos para tal caso. Para gerar uma instância 5D como a desejada de forma aleatória novamente usamos geraEsferas1Casca[ ].

Figura 34 -Testes em 5D para interseção de 2 esferas e 1 casca esférica.

A figura acima mostra que, como não temos informações geométricas do problema em uma forma natural, fica difícil deduzirmos a partir dos dados de saída quais são o raio e o centro do resultado obtido. Isso impossibilita buscarmos estender tal abordagem de forma adequada para o caso de acrescentarmos uma segunda casca esférica ao problema (1.4). Mesmo no caso 3D não temos uma maneira adequada de estender a abordagem clássica neste sentido. Essa limitação torna inviável tratarmos certos problemas de aplicação em que os aspectos geométricos podem trazer informações importantes, como é o caso do cálculo de estruturas de moléculas. Em tais situações a abordagem com a AGC tem levado a resultados promissores. No próximo capítulo veremos como é possível lidar com o problema via AGC quando acrescentamos uma segunda casca esférica. Vale lembrar que esse casso não é tratado de forma eficiente sob a abordagem clássica.

Interseção entre esferas e cascas esféricas via AGC

Neste capítulo investigamos o efeito de se acrescentar uma casca esférica extra ao problema de interseção entre duas esferas e uma casca esférica no R 3 , caso não tratado pela abordagem clássica. Este problema tem particular importância devido à sua proximidade com as aplicações relacionadas ao DMDGP, quando consideramos as incertezas vindas dos experimentos de RMN. Os testes computacionais realizados mostram o potencial da abordagem proposta com respeito a busca de generalizações para os problemas vistos no Capítulo 1. Ao longo deste capítulo, continuaremos seguindo as notações usadas anteriormente. Ressaltamos que, de acordo com a Figura 15, dependendo da configuração, poderíamos ter outros resultados para interseção do círculo κ com a casca esférica S 3 . Estaremos assumindo que o resultado desta etapa é o par de arcos determinado por (4.21), que denotaremos por ξ d . A saber, 

Interseção de esferas e duas cascas esféricas

ξ d = p p d ∈ R 4,1 : p p d = κ ∧ σ d , d ∈ [d 3 , d 3 ] , ( 5 
τ ∈ R 4,1 : τ = κ ∧ σ d ∧ σ r , d ∈ [d 3 , d 3 ], r ∈ [d 4 , d 4 ] .
(5.4)

Observações. Notemos que a solução acima é uma restrição do par de arcos ξ d . Ou seja, a solução é um subconjunto de ξ d . A solução obtida em (5.4) equivale à interseção entre os pares de arcos ξ d e ξ r . Além disso, o produto externo em (5.4) realiza a interseção entre as cascas esféricas σ d e σ r e o círculo κ, de forma que a parte do círculo que não pertença à solução seja desconsiderada.

Cascas esféricas auxiliares

Vejamos como simplificar a solução obtida em (5.4).

Um resultado conhecido para interseção de dois intervalos reais As extremidades do par de arcos ξ d podem ser obtidas através do uso de matrizes [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF], ou pela fórmula (2.34). Logo, por (4.18) e (4. [START_REF] Aragón-Camarasa | Clifford Algebra with Mathematica[END_REF],

p - * p 1 = κ ∧ σ 3 - * = p 1 ∧ p 2 , p - * p 2 = κ ∧ σ 3 - * = p 3 ∧ p 4 .
Figura 35 -Diagrama com as cascas esféricas auxiliares.

De posse dos pontos p 1 , p 2 , p 3 e p 4 1 determinamos os raios das cascas esféricas auxiliares σ a e σ b para a situação descrita no diagrama da Figura 35: 

σ a = a 4 - r 2 a 2 e ∞ , σ b = a 4 - r 2 b 2 e ∞ , ( 5 
   (σ a i ) 2 σ a i • e ∞ 2    , r 2 a = max i=1,3    (σ a i ) 2 σ a i • e ∞ 2    , ( 5.7) 
onde

σ a i = p i • a 4 ∧ e ∞ , para i = 1, 3.
Os valores de r b e r b são definidos de forma análoga,

r 2 b = min i=2,4    (σ b i ) 2 σ b i • e ∞ 2    , r 2 b = max i=2,4    (σ b i ) 2 σ b i • e ∞ 2    , ( 5.8) 
onde As cascas auxiliares σ a e σ b em (5.6) são tais que

σ b i = p i • a 4 ∧ e ∞ , para i = 2,
σ a ra=r a ∩ κ = σ a ∧ κ = p 3 ∧ p 3 , σ a ra=ra ∩ κ = σ a ∧ κ = p 1 ∧ p 1
1 Adiante mostraremos como identificar estes pontos algebricamente.

2 Adiante veremos como obter os arcos s 1 e s 2 de forma explícita. 

∩ κ = σ b ∧ κ = p 2 ∧ p 2 , σ b r b =r b ∩ κ = σ b ∧ κ = p 4 ∧ p 4 .
Isso mostra que, embora as cascas esféricas auxiliares gerem os arcos s 1 e s 

σ a ∩ s 1 = s 1 , ( 5.9 
)

σ b ∩ s 1 = s 2 .
(5.10)

Após construir as cascas esféricas auxiliares (5.6), comparamos os raios destas com os raios das cascas interna e externa de S 4 , i.e., com r = d 4 , d 4 . Nesta etapa, temos as seguintes possibilidades:

(i) r < r i ; (ii) r i ≤ r ≤ r i ; (iii) r i < r < r j ; (iv) r i ≤ d 4 ≤ r i e r j ≤ d 4 ≤ r j ; (v) r i > r b , para r = d 4 , d 4 , i, j = a, b e i = j.
Por fim, usando (5.5), determinamos a solução do problema: 

τ ∈ R 4,1 : τ = κ ∧ σ d ∧ σ r ab , d ∈ [d 3 , d 3 ],

Obtendo um par de arcos explicitamente

Através de (2.34), podemos obter o par de arcos s 1 e s 2 que formam ξ d (5.1):

s 1 = p - * p d -p - * p d • p - * p d e ∞ • p - * p , ( 5.12 
) Figura 36 -Testes das expressões para o par de arcos.

s 2 = -p - * p d + p - * p d • p - * p d e ∞ • p - * p d , ( 5 

Testes computacionais

A fim de testarmos o que foi apresentado acima, vejamos um problema adaptado de [START_REF] Alves | Álgebra de Clifford Aplicada ao Cálculo de Estruturas Moleculares[END_REF], em que a versão original foi resolvida utilizando rotores Na figura acima vemos que, embora as cascas auxiliares forneçam os pares de arcos s 1 e s 2 , surge uma parte que pode não pertencer à solução. Adiante, na etapa final da obtenção da solução, as partes indesejadas serão ignoradas por meio da interseção através do produto externo, conforme (5.9) e (5.10). De fato, tendo obtido os par de arcos s 1 e s 2 , o efeito da interseção com a segunda casca esférica é de restringi-los.

Por (5.15), (5.16) e definição da casca esférica S 4 representada por σ r (5.2), temos que

r a ≤ d 4 ≤ r a , r a < d 4 < r b .
Logo, os raios das cascas esféricas auxiliares e de S 4 estão de acordo com as condições (ii) e (iii), mencionadas anteriormente. Então, usando (5.5), obtemos o parâmetro que será usado na solução do problema:

r ab ∈ [max{r a , d 4 }, min{r a , d 4 }].
Ou seja,

r ab ∈ [1.772, 1.79].
Portanto, a solução procurada é dada por 

Utilizando a abordagem via AGC em aplicações

Vejamos como realizar a interseção entre duas esferas e duas cascas esféricas no R 3 utilizando as ideias descritas anteriormente e como este problema pode aparecer na principal aplicação considerada neste trabalho. Caso geral. A fim de fixar a notação, inicialmente reapresentaremos algumas definições já vistas. Na busca de simplificar o exemplo de aplicação, agora usamos uma forma mais compacta para as definições usuais.

Denotemos por S 1 e S 2 duas esferas e por S 3 e S 4 duas cascas esféricas no R 3 . Estaremos assumindo que o conjunto formado por todos os centros é L.I. Usando a mesma notação vista anteriormente na abordagem via AGC, a interseção do círculo κ = σ 1 ∧ σ 2 com a casca S 3 é dada por

p p d ∈ R 4,1 : p p d = κ ∧ σ 3 , d 3 ∈ [d 3 , d 3 ] ,
onde σ 3 é a representação dual de S 3 .

Portanto, a solução da interseção entre as duas esferas e as duas cascas esféricas pode ser expressa por . Pontos que não satisfazem estas condições são descartados por meio do produto exterior usado para realizar a interseção, assim como antes. A Figura 42 ilustra este procedimento em um caso em que tivemos infactibilidade para todos pontos em s 5 mas factibilidade para todos x 5 em s 5 . Já a figura abaixo ilustra um caso em que, sob a configuração das distâncias intervalares envolvidas, as posições factíveis para x 5 são apenas uma parte do arco s 5 .

{τ ∈ R 4,1 : τ = κ ∧ σ 3 ∧ σ 4 , d 3 ∈ [d 3 , d 3 ], d 4 ∈ [d 4 , d 4 ]}, ( 5 
Figura 43 -Esquema de árvore iBP envolvendo poda (2). Dessa maneira, as posições factíveis x 5 devem satisfazer o seguinte sistema não-linear Logo, desejamos encontrar todos os x ∈ R 3 tais que Isso mostra que a posição x 8 irá depender dos pontos escolhidos anteriormente nos arcos que obtivemos como solução em cada nível precedente. Como, a partir do quarto nível, temos pares de arcos como possíveis posições, nosso problema deixa de ser discretizável. Com o uso da AGC, podemos descrever os pares de arcos em termos de parâmetros conhecidos a priori e tratar o resultado das interseções sem a necessidade do processo de amostragem. Uma forma de incorporar essa característica de forma explícita é analisando a dependência de x 8 com respeito às posições anteriores, sendo sua posição obtida em termos das distâncias intervalares antecessoras ao oitavo nível. Dessa maneira, podemos representar a solução de (5.19) por 

                       ||x 5 -x 4 || = d 4,5 , ||x 5 -x 3 || = d 3,5 , d 2,5 ≤ ||x 5 -x 2 || ≤ d 2,5 , d 1,5 ≤ ||x 5 -x 1 || ≤ d 1,5 ,
               ||x -x 7 || = d 7,
x = x 8 (d i-3,i , d i-2,i , d i-1,i ) ∈ s 8 ∪ s 8 , onde d i-1,i , d i-2,i ∈ R + e d i-3,i ∈ [d i-3,i , d i-3,i ], para i = 4,

Testes computacionais em um problema de aplicação

A fim de testar o que foi feito anteriormente, vejamos um exemplo onde temos interseções envolvendo duas cascas esféricas.

Instância considerando distâncias intervalares e um centro móvel. Consideremos um DMDGP intervalar cujos dados de entrada são: Devido às características do problema, podemos fixar os três primeiros átomos, de forma que

d i-1,i = 1, d i-2,i = √ 3, para i = 3,
x 1 = [0 0 0], x 2 = [-1 0 0], x 3 = [-1.5 √ 3 2 0].
Quarto átomo. Seguindo o algoritmo BP, o próximo passo é determinar a posição x 4 , o que equivale a resolver o sistema não-linear

               ||x 4 -x 3 || = d 3,4 , ||x 4 -x 2 || = d 2,4 , d 1,4 ≤ ||x 4 -x 1 || ≤ d 1,4 .
Usando a AGC, o problema acima se reduz a obter τ 4 ∈ R 4,1 dado por 

τ 4 = σ 3,4 ∧ σ 2,4 ∧ σ 1,4 , (5.22) onde σ i,4 = c i - d 2 i,4 2 e ∞ , i = 2, 3 e σ 1,4 = c 1 - d 2 1,4 2 
               ||x 5 -x 4 || = d 4,5 , ||x 5 -x 3 || = d 3,5 , d 2,5 ≤ ||x 5 -x 2 || ≤ d 2,5 .
O problema acima via AGC é dado por A figura acima mostra que a solução dada por (5.26) é a mesma que a obtida via cascas esféricas auxiliares (5.25). Já a Figura 45 mostra os valores obtidos nas etapas para obtenção da solução. Ressaltamos que os valores estão de acordo com o esperado. Na última etapa para determinar a qual parte do par de arcos (5.26) pertence a solução, podemos usar o teste de inclusão descrito em [START_REF] Cameron | Oriented conformal geometric algebra[END_REF], ou então testar as extremidades dos arcos envolvidos, usando o que vimos nas seções anteriores.

τ 5 = σ 4,5 ∧ σ 3,5 ∧ σ 2,5 , (5.23) onde σ i,5 = c i - d 2 i,5 2 e ∞ , i = 3, 4 e σ 2,5 = c 2 - d 2 2,5 2 
Na Figura 45 a variável Pab5 1b corresponde a uma das partes do par de arcos avaliado em r ab = r ab . Assim como antes, tal par de arcos foi obtido pela interseção do círculo κ = σ 4,5 ∧ σ 3,5 com a casca esférica σ Assim como feito anteriormente, para encontrar x 6 , precisamos resolver

               ||x 6 -x 5 || = d 5,6 , ||x 6 -x 4 || = d 4,6 , d 3,6 ≤ ||x 6 -x 3 || ≤ d 3,6 .
Ou seja, temos que obter

τ 6 = σ 5,6 ∧ σ 4,6 ∧ σ 3,6 ,
(5.28) Tendo escolhido x 6 , precisamos resolver A solução denominada "exata" na figura acima se refere a conformação molecular correspondente aos valores médios das distância intervalares usadas como entrada da instância a ser resolvida. Neste exemplo as soluções para o problema dependem dos raios das cascas esféricas que surgem ao longo de cada etapa do BP. Basicamente, para gerar os dados de entrada do exemplo visto, alteramos uma instância presente em [START_REF] Lavor | Álgebra e Geometria no Cálculo de Estrutura Molecular[END_REF], considerando distâncias intervalares adicionais, sendo estas construídas a partir de uma pequena variação em um conjunto de distâncias precisas. Ressaltamos que, como as soluções encontradas em cada nível no caso intervalar não são pontos, mas arcos, par de arcos, calotas esféricas, entre outras possibilidades, para que testemos se o conjunto solução dos possíveis valores para x i , para i = 1, . . . , 8, contém de fato os pontos correspondentes a solução "exata" fixada, uma opção é variar as posições encontradas levando em conta todos os valores possíveis para seus parâmetros. Isso equivale a variar os raios das cascas esféricas usadas na obtenção da solução, entre todos os valores para factibilidade de x i . Vemos pela figura acima que ao assumir que o centro x 4 é móvel, i.e., está variando dentre todos os seus valores possíveis, o efeito sob as possíveis posições para x 5 é que, em vez de termos um arco, ou par de arcos, como possibilidades para x 5 , teremos uma calota esférica. Continuando o processo de variar os centros móveis, obtemos parte de uma esfera sólida como as regiões de factibilidade para posição do átomo em questão. Notemos que um dos pontos da calota na Figura 52 é a solução fixada inicialmente para x 5 , ilustrando que o conjunto solução (5.26) está de acordo com o esperado. Observações. A fim de obter todas as posições que formam a solução do problema, podemos usar a estratégia acima para obter um conjunto com maior número de possibilidades, dentre as possíveis. Ou seja, para determinar x i , para i = 5, . . . , 8, de forma que coincida com a solução "exata", podemos considerar os centros x i-1 como sendo móveis. Dessa maneira, no lugar de termos apenas um arco de possibilidades para x i , teremos uma calota esférica. Dependendo do nível analisado, há a possibilidade de considerar variações não apenas em x i-1 , mas também em x i-2 e x i-3 , sendo que a região gerada pela variação dessas posições, usadas para definir os centros das cascas esféricas, passam a ser mais gerais do que um arco restrito a um círculo, ou uma calota esférica. Este aspecto geométrico é o mesmo que descrevemos inicialmente quando analisamos a expressão (5.20) para x 8 .

onde σ i,6 = c i - d 2 i,6
               ||x 7 -x 6 || = d 6,7 , ||x 7 -x 5 || = d 5,7 , d 4,7 ≤ ||x 7 -x 4 || ≤ d 4,

Movendo os centros x

6 Considerações Finais

Contribuições

Este trabalho apresentou uma nova abordagem via AGC para se obter a interseção de esferas e cascas esféricas. Na literatura comumente se usam rotores. Os resultados obtidos mostraram-se adequados na busca de generalizações a espaços nD de resultados conhecidos em 3D e, também, no caso de aplicações, principalmente em problemas envolvendo cascas esféricas. As simulações feitas para o problema de conformação molecular em espaços 3D, mostraram que a abordagem desenvolvida é promissora e possui potencial para lidar com variações do problema de forma bastante natural. Vimos que, por meio de testes computacionais, há vantagens da AGC comparada com a abordagem clássica, principalmente quando lidamos com as cascas esféricas.

Além disso, obtivemos generalizações para o caso nD de resultados da AGC já conhecidos na literatura para espaços 3D. Por exemplo, simplificações para análise do raio de uma esfera e a interseção de esferas via produto exterior para o caso geral. Também, propusemos expressões com a AGC para descrever objetos de particular interesse quando lidamos com o DMDGP, como a expressão que descreve um par de arcos. Isso trouxe vantagens consideráveis para o algoritmo iBP, ao lidarmos com as incertezas nos dados de entrada. As cascas esféricas auxiliares possibilitaram melhorias computacionais, comparando com os resultados já conhecidos na literatura. Ilustramos isso com um exemplo para o qual a abordagem clássica se tornaria inviável, pois teríamos que lidar com o processo de amostragem ao longo das etapas do algoritmo BP. As construções via AGC deste trabalho foram deduzidas de forma a tratar com esferas de raios intervalares ou precisos. Ressaltamos que, na abordagem clássica, baseada na álgebra linear, isso não ocorre. Os diferentes casos que surgem ao lidarmos com as cascas esféricas tornam as extensões da abordagem clássica praticamente intratáveis para resolver problemas com múltiplas cascas esféricas.

No caso do iBP, apresentamos um exemplo que engloba várias características presentes no DMDGP quando os centros das esferas são móveis, mostrando o potencial de aplicação da abordagem desenvolvida em instâncias mais realistas. O exemplo foi resolvido pela abordagem proposta neste trabalho e ilustra um caso onde a abordagem clássica do iBP encontraria sérias dificuldades. Embora haja versões que incorporem a AGC ao algoritmo BP, desconhecemos até o momento uma implementação que utilize a AGC no BP e permita uma extensão natural ao caso intervalar.

Sobre algumas dificuldades encontradas

Vejamos algumas dificuldades que surgiram ao longo deste trabalho e como procuramos lidar com elas.

As diferentes configurações possíveis e uma terceira casca esférica. De posse de uma forma eficiente de realizar a interseção entre duas esferas e duas cascas esféricas no R 3 , desejamos investigar o efeito de acrescentarmos mais uma casca esférica extra ao problema. As diferentes possibilidades nesta etapa estão relacionadas aos cenários descritos na Figura 15. O resultado final depende dos objetos obtidos nas etapas iniciais. Por exemplo, se o resultado da interseção entre duas esferas e uma casca for somente um arco em vez de um par de arcos, ao acrescentarmos uma nova casca teremos novas possibilidades para o resultado desta etapa. Logo, os resultados são semelhantes aos já apresentados no Capítulo 5, porém não são idênticos. A fim de cobrir o maior número possível de cenários associados ao problema real, é necessário realizarmos um estudo minucioso sobre as diferentes possibilidades para interseção entre duas esferas e duas cascas esféricas. Ressaltamos que, embora haja muitas possibilidades para tal interseção envolvendo múltiplas cascas esféricas, as pesquisas aqui realizadas dão indícios de que a abordagem desenvolvida possa ser aplicada aos diferentes casos de forma eficiente.

Duas cascas esféricas em um espaço nD e a fatoração dos blades. Enquanto certas generalizações da abordagem proposta no Capítulo 5, visando aplicações em um espaço 3D, mostram indícios de serem promissoras, ao assumirmos espaços nD nos deparamos com dificuldades consideráveis. Isso porque é desejável evitar a decomposição dos blades obtidos em cada etapa das interseções. Quando lidamos com espaços nD, a interseção entre duas esferas e duas cascas esféricas, pode resultar em uma união de subespaços que não seja o par de arcos. Para a busca de generalizações como essas é necessária uma pesquisa detalhada sobre os elementos da AGC a se considerar nas construções a serem realizadas. Por exemplo, obter uma nova fórmula para cálculo da distância entre dois pontos no espaço conforme que passe a fornecer a distância entre dois subespaços quaisquer, sendo que essa nova versão possa ser implementada e validada computacionalmente.

Próximos passos

Como os resultados obtidos se mostraram bastante adequados se comparados à abordagem usual, em que se usa álgebra linear, consideramos que a AGC possui potencial para lidar com os problemas de aplicações aqui vistos. Dentre as possibilidades para dar continuidade ao trabalho, destacamos que em uma próxima oportunidade gostaríamos de explorar os aspectos computacionais tendo uma maior proximidade com dados de entrada vindos de experimentos reais. Tendo realizado uma maior variedade de simulações ligadas a problemas reais, poderíamos reforçar os aspectos positivos já obtidos e rever as possíveis causas de dificuldades. Pesquisas com esse caráter permitiriam aproximarmos cada vez mais as contribuições aqui feitas nas áreas como a química e biologia.

No aspecto teórico, temos interesse em validar as contribuições em espaços nD para valores de n tão grandes quanto os problemas reais necessitem. Para isso, é necessário investigar tanto aspectos teóricos (o que de certa forma já fizemos tendo como base boa parte da literatura na área disponível até o momento) assim como buscar implementações eficientes. Isso permitiria que os experimentos computacionais a serem realizados não tragam limitações ao que for proposto em caráter teórico. Essas questões estão relacionadas a muitos e variados temas atuais de pesquisa na área de AGC.

A fim de obter uma abordagem onde não seja necessário fatorar os blades, devemos pesquisar a resolução de sistemas de desigualdades via AGC. Outro aspecto a explorar nesse sentido, é descrever as cascas esféricas por meio da interpolação utilizando elementos da AGC, e então buscar uma maneira de lidar com as interseções em espaços nD.

Anexos Teste de independência linear usando a AGC

A seguir temos a demonstração de alguns resultados usados ao longo dos nossos estudos [START_REF] Mcdonald | Linear and Geometric Algebra[END_REF].

Teorema. Seja {v 1 , . . . , v p } ⊆ R k um conjunto de 1-blades (vetores) L.I. Então, v 1 ∧ . . . ∧ v p é um blade de grau p.

Demonstração: Usando o processo de ortogonalização de Gram-Schmidt em {v 1 , . . . , v p } podemos construir o conjunto ortogonal {b 1 , . . . , b p }, onde

b 1 = v 1 b 2 = v 2 - v 2 • v 1 v 1 • v 1 v 1 b 3 = v 3 - v 3 • v 1 v 1 • v 1 v 1 - v 3 • v 2 v 2 • v 2 v 2 . . . b p = v p - p-1 i=1 v p • v i v i • v i v i .
Então,

v 1 = b 1 v 2 = b 2 + v 2 • v 1 v 1 • v 1 v 1 v 3 = b 3 + v 3 • v 1 v 1 • v 1 v 1 + v 3 • v 2 v 2 • v 2 v 2 . . . v p = b p + p-1 i=1 v p • v i v i • v i v i .
Logo, usando que v 1 = b 1 e as expressões acima, temos que

v 1 ∧ v 2 = b 1 ∧ b 2 + v 2 • b 1 b 1 • b 1 b 1 = b 1 ∧ b 2 + v 2 • b 1 b 1 • b 1 b 1 ∧ b 1 = b 1 ∧ b 2 , e v 1 ∧ v 2 ∧ v 3 = b 1 ∧ b 2 b 3 + v 3 • b 1 b 1 • b 1 b 1 + v 3 • v 2 v 2 • v 2 v 2 = b 1 ∧ b 2 ∧ b 3 - v 3 • b 1 b 1 • b 1 b 2 ∧ b 1 ∧ b 1 + v 3 • v 2 v 2 • v 2 b 1 ∧ b 2 ∧ v 2 = b 1 ∧ b 2 ∧ b 3 .
Na segunda igualdade acima usamos o fato de que b i ∧ b i = 0, para i = 1, 2. Além disso, usamos que b 1 ∧ b 2 ∧ v 2 = 0, pois, como v 2 é da forma α 1 b 1 + b 2 , onde α 1 é um escalar, então

b 1 ∧ b 2 ∧ v 2 = α 1 b 1 ∧ b 2 ∧ b 1 + b 1 ∧ b 2 ∧ b 2 = 0.
Seguindo esta construção, temos que

v 1 ∧ • • • ∧ v p = b 1 ∧ • • • ∧ b p .
Como o lado direito da igualdade acima é um blade de grau p, isso mostra o teorema.

Usando o produto exterior temos uma forma direita de testar quando um conjunto de vetores é L.I.: Então, a expressão

v 1 ∧ • • • ∧ v j ∧ • • • ∧ v p = v 1 ∧ • • • ∧ p i=1,i =j α i v i ∧ • • • ∧ v p
se anula, contrariando nossa hipótese. Portanto, U é L.I.

A

  fim de fixar notação, vejamos algumas definições e nomenclaturas que usaremos ao longo deste trabalho.Dizemos que um subconjuntoH do R n é um subespaço afim (ou variedade afim) se H = ∅ e se λx + (1 -λ)y ∈ H para todo x, y ∈ H e λ ∈ R. Dado um espaço afim H dizemos que T -a (H) = H 0 é o subespaço vetorial associado a H, sendo que a ∈ H e T -a : R n → R n é definida por T -a (x) = xa. A dimensãodo subespaço afim H é definida como sendo a dimensão do espaço vetorial H 0 . Ressaltamos que todo subespaço vetorial é um subespaço afim. Por outro lado, um subespaço afim nem sempre é um subespaço vetorial. Dizemos que o conjunto S(a, r) = {x ∈ R n : ||x -a|| = r} é uma esfera de centro a ∈ R n e raio r ∈ R + 1 . Às vezes, denominamos S(a, r) de n-esfera do R n . Definimos uma k-esfera no R n de centro c ∈ R k e raio r ∈ R + como sendo o conjunto {x ∈ R n : k j=1

  0 se, e somente se,α 1 = • • • = α p = 0. Dado um conjunto de pontos A = {a 1 , . . . , a p } ⊆ R n , definimos o invólucro afim de A por aff(A) =    k i=1 α i a i :

Figura 3 -

 3 Figura 3 -Possibilidades para os centros das esferas.

. 2 ) 1 R 2 R

 212 onde α k ∈ R e ξ k indica o k-vetor que faz parte de ξ. A dimensão de R n é a soma das dimensões de cada uma de suas partes k R n , sendo k = 0, 1, . . . , n. Portanto, R n tem dimensão igual a blades como sendo os multivetores que podem ser fatorados através do produto exterior de 1-vetores. Os blades são obtidos em termos da base do espaço multivetorial (2.1). Ressaltamos que nem todo k-vetor é um k-blade. Os k-vetores são combinações lineares dos k-blades de base, sendo que alguns não podem ser fatorados usando o produto exterior. Por exemplo, o bivetor e 1 ∧ e 2 + e 3 ∧ e 4 não é um blade. Já e 1 ∧ e 2 + e 2 ∧ e 4 = (e 1 -e 4 ) ∧ e 2 é um blade. Vejamos alguns exemplos de elementos de R n . O blade de grau zero ξ = 1 pertence a 0 R n , i.e., é um escalar. Como ξ = e 3 ∈ n , então ξ = e 3 é um vetor que pertence ao espaço vetorial 1 R n . Já ξ = e 2 ∧ e 3 ∈ n é um blade de grau dois.

2 R

 2 n é um espaço bivetorial, ou seja, formado por bivetores. O k-vetor ξ = e 1 ∧ e 2 ∧ • • • ∧ e k ∈ k R n é um blade de grau k. Ressaltamos que cada espaço k R n contém todos k-vetores do espaço multivetorial R n .

Figura 6 -

 6 Figura 6 -Exemplo do produto exterior gerando subespaços orientados[START_REF] Fernandes | Álgebra Geométrica e Aplicações[END_REF].

  é a menor esfera que contém σ. Ressaltamos que o raio e centro de σ n são iguais aos de σ. Embora e ∞ • σ não seja necessariamente igual a -1 para o caso geral, temos que e ∞ • σ n = -1.

Figura 8 -

 8 Figura 8 -Alguns versores.

  2, denota a representação dual do plano cartesiano no espaço conforme. A Figura 8 mostra a expressão para π i . Análogo a (2.26), de forma geral, o rotor definido por a e b em termos do produto geométrico é dado por R = ba. O rotor R tem o papel de rotacionar um elemento com respeito ao plano orientado determinado pelo bivetor B. De fato, na definição (2.26) a parte escalar diz respeito ao quanto será rotacionado, enquanto a parte bivetorial informa a maneira que é feita a rotação.

Figura 9 -

 9 Figura 9 -Testes com o CLUCalc para um rotor.

Figura 10 -

 10 Figura 10 -Saída do CLUCalc para testes com o rotor.

Figura 11 -

 11 Figura 11 -Testes com o CLUCalc.

  e do join. Suponha que desejamos realizar a interseção entre dois subespaços representados pelos blades A e B. Denotemos por M a parte comum entre os blades A e B. Ou seja, M = A ∩ B. Por definição M é um blade. Já que M é a interseção entre A e B, este é o maior subespaço que pertence tanto a A quanto a B. Por outro lado, denotemos por J o menor subespaço que contém os subespaços A e B. Logo, J = A ∪ B.

Figura 12 -

 12 Figura 12 -Configurações para a interseção dos blades a e B.

3. 1

 1 Primeiro método -centros L.I. Assim como em (1.1), consideremos n esferas S i (a i , d i ) no R n de raios d i , cujos centros a i são L.I., sendo i = 1, . . . , n. Para obtermos a interseção destas n esferas temos que resolver o sistema (1.1) com m = n. Ou seja, temos que obter os pontos x ∈ R n , tais que ||x -a i || 2 = d 2 i , (3.1) onde i = 1, . . . , n. Como {a i } n i=1 é L.I., a matriz cujas colunas são os centros a i , i.e., A = a 1 , . . . , a n , é não-singular. Expandindo (3.1), ficamos com

  y ∈ R n-1 e z ∈ R. Então, reescrevemos (3

  Dessa maneira, a matriz n × (m -1) cujas colunas são os centros em Ā dada por Ā = a 1 -a m , . . . , a m-1 -a m é tal que posto( Ā) = k. Ou seja, Ā pode não ter posto completo. Suponhamos que o ponto x ∈ R n esteja na interseção das m esferas, i.e., satisfaz (3.1). Então, após a translação de x por -a m , temos que x = xa m está na interseção das esferas, ||x -(a i -a m )|| 2 = d 2 i , (3.15) para i = 1, . . . , m. Em particular, quando i = m, ||x|| 2 = d 2 m . (3.16) Expandindo (3.15), temos que

  y = c.(3.21) Como Rt tem posto completo 2 , o sistema acima tem solução única se c está na imagem de Rt3 . Caso contrário, o sistema (3.19) não tem solução e a interseção entre as m esferas é vazia. Suponhamos que (3.21) tenha solução. Então usando a definição de x e de w em (

. 24 )

 24 onde ρ 2 = d 2 m -||y|| 2 . Portanto, analisando o lado direito da expressão acima, temos um dos seguintes casos para a solução: (i) se ρ 2 < 0, a solução é vazia; (ii) se ρ 2 = 0, então 2 De fato, a matriz Rt é (m -1) × k e tal que posto( Rt ) = posto( R) = posto( Ā) = k. Notemos que, por um lado, posto(A) = posto(QR) ≤ posto(R). Por outro, posto(R) = posto(Q t A) ≤ posto(A). Portanto, como R tem k colunas não nulas, isso mostra que posto( Ā) = posto(R) = posto( Rt ) = posto( R) = k. 3 Isto é uma consequência de que a decomposição QR da matriz Ā é dada por

  Temos duas possibilidades para o invólucro afim do conjunto formado por todos os centros, i.e., deC = A ∪ {a m+1 }: dim(aff(C)) = k + 1; ou dim(aff(C)) = k. Primeiro caso. Suponhamos que dim(aff(C)) = k + 1. Então, transladando os centros A por -a m , obtemos o conjunto Ā = {a 1 -a m , . . . , a m-1 -a m }. Como dim(aff(A)) = k,podemos supor, s.p.g, que o conjunto formado pelos k primeiros elementos e o último elemento de Ā é L.I. Assim, a matriz Ā = ā1 , . . . , ām , (3.26) onde āi = a i -a m , para i = 1, . . . , m -1, e ām = a m+1 -a m , tem posto k + 1. Seja E a matriz de permutação que antecipa a coluna ām de Ā para a posição da coluna k + 1, e desloca as colunas k + 1 até m -k -1 para as últimas posições. Isto é, E é tal que 4 ĀE = Ā1:k , Āk+1:m-1 , ām E = Ā1:k , ām , Āk+1:m-1 . Suponhamos que x ∈ R n seja um ponto na interseção, ou seja, satisfaz (3.25). Transladando x por -a m , obtemos a solução transladada x = xa m e (3.25) assume a forma

+

  Rt y = c, c m+1 -rt k+1 y ≤ rk+1,k+1 y k+1 ≤ c m+1 -rt k+1 y, (3.34) onde c = c 1 . . . c m-1 t e c i é definido como anteriormente. Dessa maneira, assumindo que temos c ∈ Im( Rt ), então existe um único y ∈ R k determinado pela primeira equação de (3.33) de forma que β ≤ y k+1 ≤ β, acima que os valores de β e β em (3.35) dependem do sinal de rk+1,k+1 . Como Q é ortogonal e x = xa m , então (3.32) implica em x = Q a m . (3.36) Já que x é um ponto na interseção, então satisfaz o seguinte sistema ||x -

a y 2 k+1 ≤ d 2 m -||y|| 2 .Q

 222 .37) A equação acima tem solução real quando o lado direito é maior ou igual a zero. Esta condição equivale Supondo d 2 m -||y|| 2 ≥ 0, a desigualdade acima pode ser escrita como -α ≤ y k+1 ≤ α, onde α = d 2 m -||y|| 2 . Lembremos que anteriormente obtivemos a condição (3.35) para y k+1 . Assim, para que a solução exista temos que ter y k+1 ∈ β, β ∩ -α, α . Logo, se max{β, -α} ≤ y k+1 ≤ min{β, α}, (3.38) então a interseção não é vazia. Por outro lado, se β < -α, ou β > α, ou d 2 m -||y|| 2 < 0, temos que a interseção é vazia. Portanto, se a primeira equação de (3.34) tiver solução (única), para cada y k+1 satisfazendo (3.38), temos uma (n -k -1)-esfera. Neste caso, a solução obtida usando (3.36) e (3.37) é a união destas (n -k -1)-esferas, quando d 2 m -||y|| 2 > 0 e y k+1 pertencer a um intervalo não degenerado. Se temos d 2 m -||y|| 2 = 0, então a solução é um ponto.Segundo caso. Agora assumiremos que dim(aff(C)) = k. Logo, dim( Ā) = k, onde a matriz Ā tem a mesma forma que em(3.26). Computando a decomposição QR de Ā, obtemosĀ = QR = Q Q é n × n e ortogonal, R é k × (n -1) e tem posto completo. Então, y ∈ R k e z ∈ R n-k e Rt y = c, c m+1 ≤ rt m y ≤ c m+1 . (3.41) Observemos que, como posto de Rt é completo, quando existir (única) solução esta deve satisfazer as desigualdades em (3.41). Neste caso, a solução da interseção entre as esferas é obtida de (3.40), sendo dada por m , onde z é determinado da seguinte maneira. Sabemos que a solução x é tal que satisfaz (3.25) e, em particular, para i = m, ||x -a m || 2 = Q

4. 1

 1 Sobre o sinal do raio de uma (n-k)-esfera Para classificarmos o resultado da interseção entre esferas, podemos analisar o raio da k-esfera obtida como interseção do problema. No entanto, estaremos utilizando um resultado mais simples que é deduzido a seguir. Para analisarmos o sinal do quadrado do raio de uma (n -k)-esfera do R n representada por σ, conforme (2.21), basta analisarmos o sinal de t = σ • σ. (4.1) De fato, por (2.23), temos que o sinal do raio r da esfera σ é dado por sgn(r 2 ) = -(-1) k

para i = 1 ,

 1 . . . , k. Pelo que fizemos em (4.5) e (4.6), o sistema (4.12) equivale a ||x -āi || 2 = d 2 i , com i = 1, . . . , k. Ou seja, σ (4.11) é a representação dual de uma (n -k)-esfera do R n em R n+1,1 .

  onde ∧ ∧ ∧ denota o join. Notemos que o efeito da interseção acima é o de restringir σ (4.11).

(4. 13 )

 13 onde r = k, k + 1, . . . , m -1 e σ(k) = σ (4.11). Sendo assim, através de (4.13), realizamos a interseção de σ com as m -k esferas restantes, obtendo σ = σ(m) .

Figura 13 -

 13 Figura 13 -Interseção entre esferas no R 3 .

. 16 ) 3 2 e ∞ , σ 3 = a 3 - d 2 3 2

 16333 onde a i = e 0 + a i + ||a i || 2 2e ∞ e i = 1, . . . , m. Transladando os centros A por -a m , obtemos Ā = {ā i } m i=1 , com āi = a i -a m , i = 1, . . . , m. Vamos supor, s.p.g., que{ā i } k i=1 é L.I., onde k = dim(aff(a i )), sendo 1 ≤ k ≤ min{m -1, n}, assim como antes. Já que {ā i } k i=1 é L.I., a representação destes centros {ā i } k i=1 em R n+1,1 é L.I. Logo, as k esferas do R n representadas em R n+1,1 por {σ i } k i=1 formam um conjunto L.I. e a interseção é dada por (4.14), sendo: (i) vazia, se t < 0; (ii) um ponto, se t = 0; ou (iii) uma (n -k)-esfera, se t > 0.Acrescentando uma casca esférica. Assim como na abordagem clássica, temos duas possibilidades para a dimensão do invólucro afim do conjunto formado por todos os centros, i.e., de C = A ∪ {a m+1 }. Primeiro caso. Suponhamos que dim(aff(C)) = k + 1. Então, transladando os centros C por -a m , definimos o conjunto C = a 1 -a m , . . . , a m-1 -a m , a m+1 -a m . Como dim(aff(C)) = k, podemos supor, s.p.g., que o conjunto formado pelos k primeiros elementos de C e {a m+1 } formam um conjunto L.I.Usando a casca esférica parametrizada pelo raio para obter arcos. Vejamos como obter a interseção entre duas esferas S 1 (a 1 , d 1 ) e S 2 (a 2 , d 2 ) e uma casca esféricaS 3 (a 3 , d 3 , d 3 ) no R 3 ,onde usamos a mesma notação descrita acima. Suponhamos que os centros {a i } 3 i=1 sejam L.I. Dessa maneira, a interseção entre as esferas σ 1 e σ 2 (4.16), é o círculo κ = σ 1 ∧ σ 2 , (4.17) assumindo que t = κ • κ > 0. Então, fazendo a interseção de κ com as cascas interna σ 3 e externa σ 3 , definidas como em (4.16), i.e., σ 3 = a 3 -d 2 e ∞ , obtemos os pares de pontos p p 1 e p p 2 , p p 1 = κ ∧ σ 3 , (4.18)

  .21)O conjunto acima é a união dos pontos que formam os arcos no círculo κ ligando os pares de pontos p p 1 e p p 2 . Dessa maneira, concluímos que a solução do problema, fornecida por (4.21), é a união de 1-esferas quando n = 3 e k = 1. Ou seja, é a união de pares de pontos.

Figura 14 -

 14 Figura 14 -Testes com o CLUCalc para uma casca esférica.

  .22) onde d ∈ U = [d m+1 , d m+1 ] e ām+1 é a representação em R n+1,1 de ām+1 = a m+1 -a m . Então, para cada d ∈ U , a interseção dada por τ d = σ ∧ σ d (4.23) é a representação dual de uma (n -k -1)-esfera do R n , sempre que t d = τ d • τ d > 0, para algum d ∈ U . Notemos que, pela construção aqui feita, o sinal de t d não muda de valor para qualquer d escolhido no intervalo U . Isso assegura que t d está bem definido e para determinarmos a solução basta testarmos seu sinal para apenas um d ∈ U . Portanto, usando (4.23) para algum d ∈ [d m+1 , d m+1 ], definimos t d = τ d • τ d e a solução da interseção entre as m esferas e uma casca esférica no R n é: (a) vazia, se t d < 0; (b) um ponto, se t d = 0; ou (c) a união de (n -k -1)-esferas, se t d > 0. No caso de (c), a solução é dada por

. 24 )

 24 Na expressão acima, como σ e σ d são obtidos por (4.14) e (4.22) respectivamente o conjunto (4.24) representa a união de (n-k-1)-esferas do R n . Isso mostra que o resultado obtido está de acordo com o da abordagem clássica. Os casos (a), (b) e (c) encontrados correspondem às possibilidades (i), (ii) e (iv) que são possíveis ocorrer para o problema (4.15).Segundo caso. Agora vamos assumir que dim(aff(C)) = k, onde C é como antes. Logo, por (4.14), realizando a interseção das m esferas do R n obtemos σ. Supondo que σ seja uma (n -k)-esfera, escolhemos 2 um ponto x em σ e verificamos se este satisfaz a desigualdade em(4.15). Se satisfizer, a solução do problema é σ obtida por(4.14). Caso contrário, a solução é vazia. Portanto, obtemos o item (iii) referente às possíveis soluções de (4.15).

Figura 15 -

 15 Figura 15 -Interseção do círculo com uma casca esférica no R 3 .

Figura 16 -

 16 Figura 16 -Implementação utilizada para gerar esferas.

Figura 18 -

 18 Figura 18 -Implementação do caso 3 da abordagem clássica.

Figura 19 -

 19 Figura 19 -Implementação da abordagem via AGC para o problema com esferas.

Figura 20 -Figura 21 -

 2021 Figura 20 -Gráficos dos resultados obtidos na abordagem via AGC.

Figura 23 -

 23 Figura 23 -Testes com o algoritmo BP e o BP via AGC, para n = 10, . . . , 100.

Figura 24 -

 24 Figura 24 -Implementação do BP via AGC.

Figura 26 -

 26 Figura 26 -Implementação da abordagem clássica com uma casca esférica (parte 1).

Figura 27 -

 27 Figura 27 -Implementação da abordagem clássica com uma casca esférica (parte 2).

Figura 28 -

 28 Figura 28 -Configurações para a interseção de 2 esferas e 1 casca esférica.

Figura 29 -

 29 Figura 29 -Testes com a interseção de 2 esferas e 1 casca esférica.

Figura 30 -

 30 Figura 30 -Obtendo a solução com auxílio do CLUCalc.

Figura 32 -

 32 Figura 32 -Saída dos testes com o CLUCalc.

  8, 3.7] . (4.26) Notemos que, como [2.8, 3.7] ⊆ [1.5, 3.7], a solução (4.26) é uma forma mais compacta de (4.25), visto que excluímos os pontos correspondentes a interseção vazia.

Figura 33 -

 33 Figura 33 -Ilustração da interseção de 2 esferas e 1 casca esférica.

  Consideremos duas esferas S 1 (a 1 , d 1 ) e S 2 (a 2 , d 2 ), e duas cascas esféricas S 3 (a 3 , d 3 , d 3 ) e S 4 (a 4 , d 4 , d 4 ) no R 3 . Suponhamos que os centros {a i } 4 i=1 sejam L.I. Vimos em (4.17) que a interseção de S 1 e S 2 fornece como resultado o círculo κ dado por κ = σ 1 ∧ σ 2 .

. 1 )

 1 onde σ d é a representação dual da casca esférica S 3 , assim como em (4.20). Consideremos a seguinte representação para a casca esférica S 4 , σ r = a 4r ∈ [d 4 , d 4 ] e a 4 = e 0 +a 4 + ||a 4 || 2 2 e ∞ . Então, de acordo com o que fizemos anteriormente, a interseção do círculo κ com a casca σ r pode ser: vazia; um ponto; ou o par de arcos dado por ξ r = p pr ∈ R 4,1 : p pr = κ ∧ σ r , r ∈ [d 4 , d 4 ] . (5.3) Supondo que o resultado da interseção entre a casca σ r com o círculo κ é o par de arcos ξ r (5.3), desejamos obter a interseção deste com o par de arcos ξ d (5.1). Portanto, o resultado procurado é dado por

  [a, b] e [c, d] é que: [a, b] ∩ [c, d] = [max{a, c}, min{b, d}],(5.5)onde a, b, c, d ∈ R. A fim de usar este resultado, vamos obter o par de arcos ξ d (5.1), através de cascas esféricas auxiliares centradas em um mesmo ponto.

. 6 )

 6 para r a ∈ [r a , r a ] e r b ∈ [r b , r b ], sendo r a e r a definidos como r 2 a = min i=1,3

. 13 ) 1 = s 1 d=d 3 , p 3 = s 1 d=d 3 , e p 2 = s 2 d=d 3 , p 4 = s 2 d=d 3 .

 13133233 onde p p d = κ ∧ σ d e d ∈ [d 3 , d 3 ]. Obtendo as extremidades dos arcos em ξ d . Usando as expressões acima obtemos de forma direta as extremidades dos arcos s 1 e s 2 , já que p Nas igualdades acima usamos o fato de que, como consideramos somente os pontos sobre um mesmo arco em (5.12) e (5.13), basta avaliar tais expressões para o valor do parâmetro d ∈ [d 3 , d 3 ] correspondente às extremidades dos arcos para recuperarmos os pontos nas extremidades de s 1 e s 2 .

3 .

 3 Consideremos as esferas S 1 , S 2 de centros a 1 = (-4, 0, 0), a 2 = (-3, -1.1133, 1.3268) e raios d 1 = 3.1102, d 2 = 1.3, e as cascas esféricas S 3 , S 4 , de centros a 3 = (0, 0, 0), a 4 = (-1.3720, -1.8260, 3.6596) e raios intervalares d 3 ∈ [d 3 , d 3 ] = [3.5, 3.7], d 4 ∈ [d 4 , d 4 ] = [1.772, 1.9]. Lembremos que o caso clássico não trata do problema com uma segunda casca esférica.

Figura 37 -

 37 Figura 37 -Interseção com duas cascas esféricas via AGC.

Figura 38 -

 38 Figura 38 -Interseção com a primeira casca esférica via AGC.

Figura 39 -

 39 Figura 39 -Resultados obtidos com o CLUCalc.

τ 2 ab 2 e

 22 Figura 41 -Etapas para se obter a solução.

s 4 ,

 4 Figura 42 -Esquema de árvore iBP envolvendo poda (1).

onde x 5 =

 5 Figura 44 -Esquema de árvore iBP envolvendo poda (3).

e ∞ , sendo d 2 , 5 ∈onde σ 1 , 5 = c 1 - d 2 1, 5 2

 251525 [2.20, 2.60]. Logo, x 5 é o par de arcos(5.23). Já que existe d i,5 para i < 2, devemos levar em conta essa restrição na solução(5.23). De fato, como d 1,5 ∈ [2.45, 2.55], então a solução assume a seguinte formaτ 5 = σ 4,5 ∧ σ 3,5 ∧ σ 2,5 ∧ σ 1,5 ,(5.24) e ∞ . A expressão acima fornece as possíveis posições para x 5 . A fim de ficar explícito que estamos lidando com um conjunto de posições para x 5 , podemos reescrever a solução (5.24) comoτ ∈ R 4,1 : τ = σ 4,5 ∧ σ 3,5 ∧ σ 2,5 ∧ σ 1,5 , d 2,5 ∈ [2.20, 2.60], d 1,5 ∈ [2.45, 2.55] . (5.25) Usando as cascas auxiliares 4 podemos reduzir a solução acima a τ ∈ R 4,1 : τ = σ 4,5 ∧ σ 3,5 ∧ σ (5) ab ∧ σ 1,5 , r (5) ab ∈ [2.39, 2.44], d 1,5 ∈ [2.45, 2.55] , (5.26) de forma que [r ab ] = [2.39, 2.44] ⊆ [d 2,5 , d 2,5 ] = [2.20, 2.60].

Figura 45 -

 45 Figura 45 -Reduzindo o intervalo associado a d 2,5 .

( 5 )

 5 Figura 46 -Etapas para se obter a solução.

( 5 )

 5 Figura 47 -Arcos factíveis para a solução x 5 .

Figura 48 -

 48 Figura 48 -Reduzindo o intervalo associado a d 3,6 .

τ

  Figura 49 -Reduzindo o intervalo associado a d 5,8 .

  Figura 52 -Soluções conhecidas e as soluções obtidas para o centro x 4 móvel.

Figura 53 -

 53 Figura 53 -Soluções obtidas variando o centro x i , para i = 4, 5, 6, 7.

  Corolário. O conjunto {v 1 , . . . , v p } ⊆ R k é L.I. se, e somente se, v 1 ∧ • • • ∧ v p = 0. Demonstração: Se o conjunto {v 1 , . . . , v p } ⊆ R k é L.I., pelo Teorema A, v 1 ∧ • • • ∧ v p é um p-blade,que por definição é não nulo. Reciprocamente, vamos assumir que temosv 1 ∧ • • • ∧ v p = 0 e supor que U = {v 1 , . . . , v p } é L.D. Como U é L.D., então existe um índice j ∈ {1, . . . , p} tal que v j pode ser escrito como a combinação linear dos demais elementos de U, i.e., comov j = p i=1,i =j α i v i .

  

  

  

  

  

  Possibilidades para os centros das esferas. . . . . . . . . . . . . . . . . 4 Ilustração de uma das etapas do algoritmo BP [3]. . . . . . . . . . . . . 5 Ilustração de uma das etapas do algoritmo iBP [4]. . . . . . . . . . . . 6 Exemplo do produto exterior gerando subespaços orientados [5]. . . . . 7 Representação de objetos Euclideanos no espaço conforme. . . . . . . . 8 Alguns versores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100. . . 24 Implementação do BP via AGC. . . . . . . . . . . . . . . . . . . . . . . 25 Implementação para gerar esferas e uma casca esférica. . . . . . . . . . 26 Implementação da abordagem clássica com uma casca esférica (parte 1). . . 27 Implementação da abordagem clássica com uma casca esférica (parte 2). . . 28 Configurações para a interseção de 2 esferas e 1 casca esférica. . . . . . 29 Testes com a interseção de 2 esferas e 1 casca esférica. . . . . . . . . . 30 Obtendo a solução com auxílio do CLUCalc. . . . . . . . . . . . . . . . 31 Interseção de 2 esferas e 1 casca esférica resultando em um par de arcos.

		Lista de ilustrações
	1	Exemplo de proteína no PDB: ID 2IQH, Influenza A [1]. . . . . . . . .
	2	Algumas informações sobre uma molécula de proteína [2]. . . . . . . .
	3	

9 Testes com o CLUCalc para um rotor. . . . . . . . . . . . . . . . . . . . 10 Saída do CLUCalc para testes com o rotor. . . . . . . . . . . . . . . . . 11 Testes com o CLUCalc. . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Configurações para a interseção dos blades a e B. . . . . . . . . . . . . 13 Interseção entre esferas no R 3 . . . . . . . . . . . . . . . . . . . . . . . . 14 Testes com o CLUCalc para uma casca esférica. . . . . . . . . . . . . . 15 Interseção do círculo com uma casca esférica no R 3 . . . . . . . . . . . . 16 Implementação utilizada para gerar esferas. . . . . . . . . . . . . . . . 17 Gráficos dos resultados obtidos com a abordagem clássica. . . . . . . . 18 Implementação do caso 3 da abordagem clássica. . . . . . . . . . . . . 19 Implementação da abordagem via AGC para o problema com esferas. . 20 Gráficos dos resultados obtidos na abordagem via AGC. . . . . . . . . 21 Testes com a abordagem clássica para m = 10 esferas no R 10 . . . . . . 22 Testes com a abordagem via AGC para m = 10 esferas no R 10 . . . . . . 23 Testes com o algoritmo BP e o BP via AGC, para n = 10, . . . , 32 Saída dos testes com o CLUCalc. . . . . . . . . . . . . . . . . . . . . . . 33 Ilustração da interseção de 2 esferas e 1 casca esférica. . . . . . . . . . 34 Testes em 5D para interseção de 2 esferas e 1 casca esférica. . . . . . . 35 Diagrama com as cascas esféricas auxiliares. . . . . . . . . . . . . . . . 36 Testes das expressões para o par de arcos. . . . . . . . . . . . . . . . .

  {e 1 e 2 , e 1 e 3 , e 2 e 3 }.

						.1)
	onde cada parte	k	R n em (2.1) tem dimensão	n k	, sendo que as combinações lineares de
					2
	k vetores de {e i } n i=1 definem uma base para esta parte. Por exemplo, uma base para	R 3
	é dada por				

  1,1 . A parte Euclideana tem base {e 1 , . . . , e n }, enquanto a parte conforme tem base {e 0 , e ∞ }, de forma que e i e j + e j e i = 2δ ij ,

		(2.6)
	e 0 e ∞ + e ∞ e 0 = -2,	(2.7)
	e 0 e i = -e i e 0 ,	(2.8)
	e ∞ e i = -e i e ∞ ,	(2.9)
	e 2 0 = e 2 ∞ = 0,	(2.10)
	onde i, j = 1, . . . , n. Denominamos {e 0 , e ∞ } de base nula. A base nula é caracterizada
	pelas propriedades (2.7) a (2.10) acima. Em particular, as duas últimas justificam o termo
	"nula". O fato de (2.10) ocorrer mostra que o produto interno (2.4) é não-Euclideano.

  = α 1 e 1 + α 2 e 3 + α 3 e 3 , com α i ∈ R. Sob esta nova abordagem, a translação é vista como sendo uma rotação ao longo de um eixo separado por uma distância infinita. Ou de forma alternativa, como reflexões consecutivas por planos paralelos. Notemos que, no lado direito da definição de translação (2.29), estamos manipulando algebricamente da mesma maneira tanto elementos do espaço conforme, como do espaço Euclideano. De fato, este aspecto é uma das vantagens de usarmos a AGC em diferentes contextos. Por exemplo, vimos a definição da translação no espaço conforme (2.29) tendo em mente a translação no espaço Euclideano (2.27). Caso quiséssemos transladar uma esfera, em vez de um vetor, não poderíamos aplicar a expressão (2.27) diretamente. Já na AGC a translação é generalizada de forma natural, no seguinte sentido. Para transladarmos uma esfera basta substituirmos o elemento x em (2.28) pela expressão de tal esfera no espaço conforme, i.

.28) 

onde x e x denotam, respectivamente, a representação no espaço conforme de x e x e

T b = 1 -1 2 be ∞ (2.

29) representa a translação por b e., por σ definida por (2.21). Essa facilidade vale para outras operações como rotação e reflexão, e também para outros objetos como ponto, plano e reta. A equação (2.25) codifica todos estes casos, sendo que V denota a operação atuando sobre o objeto ξ, definido de acordo com a Figura 7.

  desenvolver os termos envolvidos, obtendo os pontos p 1 e p 2 . Em[START_REF] Alves | Álgebra de Clifford Aplicada ao Cálculo de Estruturas Moleculares[END_REF] temos a demonstração deste resultado para o R 3 , que é análoga à que apresentaremos para o R n .

	Primeiramente, mostremos o seguinte,

mos extrair de p p (2.33) os pontos p 1 e p 2 , obtendo suas expressões de forma explícita através da fórmula (2.34). Na representação primal, o par de pontos é dado por p 1 ∧ p 2 . Para demonstrar (2.34), vamos substituir p - * p = p 1 ∧ p 2 no lado direito da igualdade e

  subespaços a serem intersectados, conseguimos obter a priori um blade que seja proporcional ao subespaço que contém a operação de interseção, i.e., ao join. Assim, conseguimos definir o join.Observações. Em[START_REF] Dorst | Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[END_REF], há um algoritmo de complexidade O(n 2 ) para se obter o join e meet simultaneamente para o problema de interseção de esferas. Embora, em certos problemas, esse algoritmo possa levar a uma complexidade computacional exponencial, na prática é possíveis explorarmos as características específicas do problema e reduzir o seu custo. Em nosso trabalho, uma análise das particularidades da interseção entre esferas permitiu evitarmos o uso do join.

.41) As equações (2.40) e (2.41) definem as operações de join e meet. Notemos que ambas estão relacionadas, visto que de posse do meet determinamos o join, e vice-versa. Na prática, é comum determinarmos primeiramente o join. Isso porque, através de uma análise adequada dos

  4,1 , disponibilizando diversas ferramentas gráficas. No entanto, a versão do CLUCalc usada neste trabalho não incorpora o caso de n ≥ 4. Para testes envolvendo o caso geral, i.e., o espaço R n+1,1 , usamos o clifford.m. Nos experimentos computacionais aqui realizados, analisamos o erro MDE das soluções obtidas. O erro MDE de uma solução x ∈ R n é definido por onde a i e d i são, respectivamente, o centro e raio da esfera i, sendo i = 1, . . . , m. Embora MDE seja a abreviação de mean distance error (do inglês), estaremos nos referindo a este erro por erro MDE. Quanto menor o erro MDE, melhor a precisão da solução encontrada. Adiante veremos que, embora tenhamos obtido valores baixos de erro MDE para as soluções encontradas, o tempo de execução em alguns casos não foi satisfatório 3 . Quanto ao tempo de processamento, nos deparamos com algumas dificuldades nos testes feitos com o clifford.m para m = 10 esferas. No entanto, os testes realizados mostram a validade da abordagem apresentada.

	MDE (x) =	1 m	m i=1	| ||x -a i || -d i | d i	,

  4. Denominaremos o arco indo de p 1 a p 3 de s 1 e o arco indo de p 2 a p 4 de s 2 2 . Como na construção vista não estamos levando em conta a orientação do círculo, então os arcos s 1 e s 2 continuam os mesmos se invertemos as orientações consideradas para s 1 e s 2 , i.e., são conjuntos de pontos iguais. Assim, invertendo a orientação, o arco indo de p 3 a p 1 continua sendo o arco s 1 já definido. O mesmo vale para o arco s 2 . Tendo definido as cascas auxiliares σ a e σ b , como acima, podemos obter os arcos s 1 e s 2 de ξ d de forma que, quando acrescentarmos a segunda casca esférica S 4 , o problema seja simplificado. Notemos que agora todas as cascas envolvidas nesta etapa estão centradas em a 4 . Dessa maneira, após obter o par de arcos resultante da interseção das esferas S 1 e S 2 com a casca S 3 , dado por ξ d , construímos as cascas esféricas auxiliares centradas em a 4 , através das quais obtemos estes arcos. Assim, podemos usar a análise feita em (5.5) para determinar a solução do problema quando acrescentamos a segunda casca esférica S 4 .

	Obtendo a solução.

  2 , elas também geram outros arcos que podem não ter relação com a solução do problema, i.e., geram os pontos p i . No entanto, como a solução está contida nos arcos s 1 e s 2 que formam ξ d , o efeito da interseção com a segunda casca esférica será o de restringi-los. Ou seja, a solução será um subconjunto dos arcos s 1 e s 2 já obtidos. Isso garante que a parte que possivelmente não pertença à solução seja ignorada, visto que

  r ab ∈ [r ab , r ab ] , Pela construção aqui feita, temos que [r ab , r ab ] ⊆ [d 4 , d 4 ]. Ou seja, a solução na forma (5.11) é mais compacta do que (5.4). Isso ocorre porque não realizamos a interseção de ξ d (5.1) com todos os pontos da segunda casca S 4 , associados aos raios correspondentes ao intervalo [d 4 , d 4 ], pois restringimos os raios de S 4 somente aos valores onde a interseção é não vazia. Notamos ainda que a solução é a interseção da casca esférica σ r ab com o círculo κ, descartando a parte desta interseção que não faz parte de ξ d , o que foi feito através do produto externo: κ ∧ σ d ∧ σ r ab .

			(5.11)
	onde σ r ab = c 4 -	r 2 ab 2	e ∞ e [r ab , r ab ] é obtido de acordo com as possibilidades (i) a (v) acima.
	Observações.		

  Notamos pela figura acima que, para obter a solução do nosso problema, inicialmente realizamos a interseção do círculo κ com a casca S 3 , representada por σ d . Obtemos como resultado desta etapa o par de arcos s 1 e s 2 . Em seguida, construímos as cascas esféricas auxiliares σ a e σ b , de forma que, por meio destas, possamos representar s 1 e s 2 através de cascas centradas em um mesmo ponto. Como dissemos anteriormente, nesta etapa pode surgir, além do par de arcos, uma parte que não faz parte da solução. No entanto, após termos construído a casca σ r ab , como em (5.17), na etapa final não consideramos tal parte no conjunto solução, pois realizamos a interseção desta com os arcos s 1 e s 2 , conforme (5.9) e (5.10). Esse passo é ilustrado na etapa 4 da Figura 41, e corresponde às interseções feitas via produto exterior na solução (5.17). No exemplo acima reduzimos o intervalo [d 4 , d 4 ] que faz parte da solução (5.4) ao intervalo [r ab , r ab ]. Utilizando a mesma estratégia feita com as cascas auxiliares, poderíamos ter reduzido [d 3 , d 3 ] ao invés de [d 4 , d 4 ]. Neste caso, as cascas esféricas seriam centradas em a 3 no lugar de a 4 . Embora possamos reduzir um dos dois intervalos envolvidos na solução, a construção aqui feita não possibilita a redução dos dois intervalos ao mesmo tempo.

	Observações.

  Através das cascas esféricas auxiliares podemos reduzir [d 3 , d 3 ], ou [d 4 , d 4 ], a [r ab , r ab ]. Ressaltamos que os pares de arcos solução em (5.18) podem ser obtidos explicitamente, conforme descrito anteriormente. Suponhamos que temos um DMDGP envolvendo cinco átomos, de forma que as posições dos três primeiros são conhecidas, as distâncias d 3,4 , d 2,4 são precisas e que d 1,4 ∈ [d 1,4 , d 1,4 ]. Então, no lugar de um par de pontos como possíveis soluções para o quarto vértice v 4 , temos um par de arcos

	Realizando a poda no caso de distâncias intervalares.

.18) 

onde σ 4 é a representação dual de S 4 .

Observações.

  8 , ||x -x 6 || = d 6,8 , d 5,8 ≤ ||x -x 5 || ≤ d 5,8 , = x 7 (x 6 , x 5 , x 4 ), x 6 = x 6 (x 5 , x 4 ), x 5 = x 5 (x 4 ) e x 4 ∈ s 4 ∪ s 4 . Portanto, os pontos que satisfazem (5.19) são tais que x = x 8 (x 7 , x 6 , x 5 , x 4 ) ∈ s 8 ∪ s 8 , (5.20) onde x i ∈ s i ∪ s i , para i = 4, 5, 6, 7.

	(5.19)
	onde x 7

de poda levando em conta centros móveis.

  , para i = 5, 6, 7, e os centros x 6 e x 7 são pontos fixados nos arcos correspondentes ao sexto e sétimo níveis, i.e., x i ∈ s i ∪ s i , para i = 6, 7. Suponhamos que existe uma distância d i,8 para i < 5, por exexmplo, d 4,8 ∈ [d 4,8 , d 4,8 ]. Então, pode ser que nem todos pontos em (5.21) sejam factíveis. Os pontos factíveis são obtidos por τ = σ 7,8 ∧ σ 6,8 ∧ σ 5,8 ∧ σ 4,8 , onde d 5,8 ∈ [d 5,8 , d 5,8 ] e d 4,8 ∈ [d 4,8 , d 4,8 ]. Com as cascas auxiliares, podemos reduzir [d 5,8 , d 5,8 ] de forma a continuar as próximas iterações do algoritmo BP sem usar o processo de amostragem.

		5, 6, 7, 8. Assim, com auxílio da
	abordagem via AGC, determinamos x 8 através de	
	τ = σ 7,8 ∧ σ 6,8 ∧ σ 5,8 ,	(5.21)
	onde d 5,8 ∈ [d 5,8 , d 5,8 ], σ i,8 = a i -e ∞ Aresta Observação. d 2 i,8 2	

  e ∞ , sendo d 1,4 ∈ [2.10, 2.20]. Utilizando o CLUCalc [20], computamos (5.22) para a casca interna e externa de σ 1,4 , obtendo as seguintes posições para x 4 ∈ R 3 :

	x 4 1 = [-1.21 1.61 0.60], x 4 2 = [-1.21 1.61	-0.60],
	x 4 1b = [-1.42 1.49 0.78], x 4 2b = [-1.42 1.49	-0.78].
	Como não existe d i,4 para i < 1, todas as posições acima são factíveis. Logo, escolhemos
	x 4 1 = [-1.21 1.61 0.60] para x 4 . Este valor corresponde a escolher d 1,4 = d 1,4 = 2.10
	para σ 1,4 em (5.22).	
	Quinto átomo. Agora desejamos encontrar x 5 , ou seja, devemos resolver

  2e ∞ , para i = 3, 4, 55 . Como existe d 2,6 ∈ [2.70, 2.90], então a solução (5.28) passa a ser dada porτ 6 = σ 5,6 ∧ σ 4,6 ∧ σ 3,6 ∧ σ 2,6 .A existência da distância extra d 2,6 leva a uma restrição na solução (5.28). Assim, as possíveis posições x 6 são dadas pelo conjuntoτ ∈ R 4,1 : τ = σ 5,6 ∧ σ 4,6 ∧ σ 3,6 ∧ σ 2,6 , d 3,6 ∈ [2.40, 2.60], d 2,6 ∈ [2.70, 2.90] . A fim de simplificar a notação, assumimos que σ 3,6 = σ 3,6 = c 3 -

	Usando as cascas auxiliares podemos reduzir a solução acima a
	τ ∈ R 4,1 : τ = σ 5,6 ∧ σ 4,6 ∧ σ	(6) ab ∧ σ 2,6 , r	(6) ab ∈ [2.40, 2.47], d 2,6 ∈ [2.70, 2.90]
	de forma que [r	(6) ab , r	(6) ab ] = [2.40, 2.47] ⊆ [d 3,6 , d 3,6 ] = [2.40, 2.60].
	σ 3,6 . Usaremos tal simplificação sempre que necessário.	d 2 2,6 2	e ∞ é a definição da casca esférica

5 

  ||x 8 -x 7 || = d 7,8 , ||x 8 -x 6 || = d 6,8 , d 5,8 ≤ ||x 8 -x 5 || ≤ d 5,8 . = σ 7,8 ∧ σ 6,8 ∧ σ 5,8 ∧ σ 4,8 .Ou seja, a distância de poda d 4,8 restringe a solução (5.6) a um subconjunto deste. Logo,x 8 é obtido por τ ∈ R 4,1 : τ = σ 7,8 ∧ σ 6,8 ∧ σ 5,8 ∧ σ 4,8 , d 5,8 ∈ [2.20, 2.50], d 4,8 ∈ [2.40, 2.50] .Portanto, através das cascas auxiliares, a solução acima se reduz a

	Assim como antes, x 8 é solução de		
			
	      		
	      		
	Usando a AGC, resolver o sistema acima equivale a obter	
	τ 8 = σ 7,8 ∧ σ 6,8 ∧ σ 5,8 ,	
	onde σ i,8 = c i -solução (5.6) agora ser dada por d 2 i,8 e ∞ , para i = 5, 6, 7. A existência de d 4,8 ∈ [2.40, 2.50], implica na 2
	τ 8		
		7 ,	
	para obter x 7 . Ou, de forma equivalente, computar		
	τ 7 = σ 6,7 ∧ σ 5,7 ∧ σ 4,7 ,	(5.29)
	onde σ i,7 = c i -para x 7 dadas por τ 7 (5.29). d 2 i,7 e ∞ , para i = 4, 5, 6. Logo, com a AGC, obtemos as possíveis posições 2
	Oitavo átomo. Por fim, fixemos x 7 = [-0.81	1.73	0.01] para x 7 . Esta posição
	corresponde a escolhermos		
	d 4,7 = d 4,7 = 2.10	
	em (5.29).		

Definimos R + como R + = {α ∈ R : α ≥ 0}.

Há livros em que se faz distinção entre a álgebra de Grassmann e a álgebra exterior, mas neste trabalho assumimos que ambas são sinônimos. Mais detalhes sobre essa questão podem ser encontrados em[START_REF] Vaz | An Introduction to Clifford Algebras and Spinors[END_REF].

Em anexo, temos a demonstração de que este produto exterior entre dois blades resulta em um blade.

Adiante, veremos diferentes possibilidades para realizar a interseção de esferas. No caso geral, pode ser que o produto exterior quando aplicado na forma usual, deixe de fornecer a interseção.

Aqui fica subtendido que p, c ∈ R n+1,1 sendo que estes são representações primais no modelo conforme do ponto e do centro do círculo em questão. Ressaltamos que, pela notação adotada neste trabalho, para evitar ambiguidades, os elementos escritos em negrito pertencem ao espaço Euclideano. Quando nos referirmos a um ponto p, fica subtendido que este é a representação primal do ponto p ∈ R n e que p ∈ R n+1,1 . O mesmo vale para outros elementos, como por exemplo a esfera σ.

Abreviação de "sem perda de generalidade".

A notação para o subíndice em Ā1:k indica que esta matriz é formada pelas colunas 1 a k de Ā.

Para isso, podemos usar (2.19) ou (2.20).

Assumimos como sendo insatisfatório testes computacionais que levaram mais do que 20 minutos para serem concluídos.

A única mudança com respeito ao problema original é que alteramos o intervalo [d

, d 4 ] = [1.772, 1.8] para [d 4 , d 4 ] = [1.772, 1.9], de forma a ilustrar o uso das cascas esféricas auxiliares.