Geometria discreta

Uma coleção de círculos e o gráfico de discos unitários correspondente

Geometria discreta e geometria combinatória são ramos da geometria que estudam propriedades combinatórias e métodos construtivos de objetos geométricos discretos . A maioria dos problemas em geometria discreta envolvem conjuntos discretos e conjuntos finitos de objetos geométricos básicos, tais como pontos, linhas, planos, círculos, esferas, polígonos, e assim por diante. O assunto se concentra nas propriedades combinatórias desses objetos, como como eles se cruzam ou como eles podem ser organizados para cobrir um objeto maior.

A geometria discreta tem uma grande sobreposição com geometria convexa e geometria computacional e está intimamente relacionada a assuntos como geometria finita, otimização combinatória, geometria digital, geometria diferencial discreta, teoria de geométrica de gráficos, geometria tórica e topologia combinatória .

História

Embora poliedros e mosaicos tenham sido estudados por muitos anos por pessoas como Kepler e Cauchy, a geometria discreta moderna tem suas origens no final do século XIX. Os primeiros tópicos estudados foram: a densidade de embalagens circulares de Thue, configurações projetivas de Reye e Steinitz, a geometria dos números de Minkowski e as cores dos mapas de Tait, Heawood e Hadwiger .

László Fejes Tóth, HSM Coxeter e Paul Erdős, lançaram as bases da geometria discreta .

Tópicos

Poliedros e polítopos

Um polítopo é um objeto geométrico com lados planos que existe em qualquer número de dimensões. Um polígono é um polítopo em duas dimensões, um poliedro em três dimensões, e assim por diante em mais dimensões (como um polítopo 4 em quatro dimensões ). Algumas teorias generalizam ainda mais a ideia de incluir objetos como polítopos ilimitados ( apeirotopos e pavimentações ) e polítopos abstratos .

A seguir, são apresentados alguns dos aspectos dos polítopos estudados em geometria discreta:

• Combinações poliédricas
• Polítopos de treliça
• Polinômios de Ehrhart
• Teorema de Pick
• Conjectura de Hirsch

Embalagens, coberturas e inclinações

Embalagens, coberturas e inclinações são formas de organizar objetos uniformes (normalmente círculos, esferas ou ladrilhos) de maneira regular em uma superfície ou coletor .

Um empacotamento de esferas é um arranjo de esferas não sobrepostas dentro de um espaço contido. As esferas consideradas são geralmente todas de tamanho idêntico, e o espaço geralmente é um espaço euclidiano tridimensional . No entanto, problemas de empacotamento de esferas podem ser generalizados para considerar esferas desiguais,em um espaço euclidiano n- dimensional (onde o problema se torna empacotamento circular em duas dimensões ou empacotamento hiperesférico em dimensões mais altas) ou espaços não-euclidianos, como espaço hiperbólico .

Um mosaico de uma superfície plana é o lado a lado de um plano usando uma ou mais formas geométricas, chamados ladrilhos, sem sobreposições e sem espaços. Em matemática, os mosaicos podem ser generalizados para dimensões superiores.

Os tópicos específicos nesta área incluem:

• Empacotamento de círculos
• Empacotamento de esferas
• Conjectura de Kepler
• Quase-cristal
• Inclinações aperiódicas
• Gráfico periódico
• Regras de subdivisão finita

Rigidez estrutural e flexibilidade

Os gráficos são desenhados como hastes conectadas por dobradiças rotativas. O ciclo gráfico C ₄ desenhado como um quadrado pode ser transformado em um paralelogramo pela força azul, de modo que é um gráfico flexível. K _3, desenhado como um triângulo, não pode ser alterado por qualquer força que lhe seja aplicada, por isso, é um gráfico rígido.

A rigidez estrutural é uma teoria combinatória para prever a flexibilidade de conjuntos formados por corpos rígidos conectados por articulações ou dobradiças flexíveis.

Os tópicos nesta área incluem:

• Teorema de Cauchy sobre poliedros
• Poliedros flexíveis

Estruturas de incidência

Sete pontos são elementos de sete linhas no plano de Fano, um exemplo de uma estrutura de incidência.

As estruturas de incidência generalizam planos (como os planos afins, projetivos e Möbius), como pode ser visto em suas definições axiomáticas. As estruturas de incidência também generalizam os análogos de dimensões mais altas e as estruturas finitas são algumas vezes chamadas de geometrias finitas .

Formalmente, uma estrutura de incidência é um trio

$C=(P,L,I).\,$

onde P é um conjunto de "pontos", L é um conjunto de "retas" e $I\subseteq P\times L$ é a relação de incidência . Os elementos de $I$ são chamados de sinalizadores. E se

$(p,l)\in I,$

dizemos que o ponto p "está na reta" $l$ .

Os tópicos nesta área incluem:

• Configurações
• Arranjos de retas
• Arranjos de hiperplanos
• Edificações

Matróides orientados

Um matróide orientado é uma estrutura matemática que abstrai as propriedades de gráficos orientados e de arranjos de vetores em um espaço vetorial sobre um corpo ordenado (particularmente para espaços vetoriais parcialmente ordenados ). Em comparação, um matróide comum (ou seja, não orientado) abstrai as propriedades de dependência comuns também a gráficos, que não são necessariamente direcionados, e a arranjos de vetores sobre corpos, que não são necessariamente ordenados.

Teoria geométrica dos gráfos

Um grafo geométrico é um gráfico no qual os vértices ou arestas estão associadas a objetos geométricos . Os exemplos incluem grafos euclidianos, o 1- esqueleto de um poliedro ou polítopo, gráficos de interseção e gráficos de visibilidade .

Os tópicos nesta área incluem:

• Desenho gráfico
• Gráficos poliédricos
• Diagramas de Voronoi e triangulações de Delaunay

Complexos simpliciais

Um complexo simplicial é um espaço topológico de um certo tipo, construído pela "colagem" de pontos, segmentos de retas, triângulos e suas contrapartes n- dimensionais (veja a ilustração). Complexos simpliciais não devem ser confundidos com a noção mais abstrata de um conjunto simplicial que aparece na teoria moderna da homotopia simplicial. A contrapartida puramente combinatória a um complexo simplicial é um complexo simplicial abstrato .

Topologia combinatória

A disciplina de topologia combinatória usou conceitos combinatórios em topologia e, no início do século XX, se transformou no campo da topologia algébrica .

Em 1978, a situação foi revertida - métodos da topologia algébrica foram usados para resolver um problema na matemática combinatória - quando László Lovász provou a conjectura de Kneser, iniciando assim um novo estudo da topologia combinatória . A prova de Lovász usou o teorema de Borsuk-Ulam e esse teorema mantém um papel de destaque nesse novo campo. Este teorema tem muitas versões e análogos equivalentes e tem sido usado no estudo de problemas de divisão justa .

• Lema de Sperner
• Mapas regulares

Treliças e grupos discretos

Um grupo discreto é um grupo G equipado com a topologia discreta . Com essa topologia, G se torna um grupo topológico . Um subgrupo discreto de um grupo topológico G é um subgrupo H cuja topologia relativa é a discreta. Por exemplo, os números inteiros Z formam um subgrupo discreto dos reais R (com a topologia métrica padrão), mas os números racionais Q não.

Uma treliça em um grupo topológico compacto localmente é um subgrupo discreto com a propriedade de que o espaço do quociente possui uma medida invariante finita. No caso especial de subgrupos do R ^n, isso equivale à noção geométrica habitual de uma treliça, e tanto a estrutura algébrica das treliças e a geometria da totalidade de todos as malhas são relativamente bem compreendidas. Resultados profundos de Borel, Harish-Chandra, Mostow, Tamagawa, MS Raghunathan, Margulis, Zimmer, obtidos entre os anos 50 e 70, forneceram exemplos e generalizaram grande parte da teoria ao conjunto de grupos de Lie nilpotentes e grupos algébricos semi - simples em um corpo local . Na década de 1990, Bass e Lubotzky iniciaram o estudo de treliças de árvores, que continua sendo uma área de pesquisa ativa.

Os tópicos nesta área incluem:

• Grupos de reflexão
• Grupos de triângulos

Geometria digital

A geometria digital lida com conjuntos discretos (geralmente conjuntos de pontos discretos) considerados modelos digitalizados ou imagens de objetos do espaço euclidiano 2D ou 3D.

Simplificando, a digitalização está substituindo um objeto por um conjunto discreto de pontos. As imagens que vemos na tela da TV, a exibição raster de um computador ou nos jornais são de fato imagens digitais .

Suas principais áreas de aplicação são computação gráfica e análise de imagens .

Geometria diferencial discreta

Geometria diferencial discreta é o estudo de contrapartes discretas de noções em geometria diferencial . Em vez de curvas e superfícies suaves, existem polígonos, malhas e complexos simpliciais . É utilizado no estudo de computação gráfica e topologia combinatória .

Os tópicos nesta área incluem:

• Operador discreto de Laplace
• Cálculo externo discreto
• Cálculo discreto
• Teoria discreta de Morse
• Topologia combinatória
• Análise de formas espectrais
• Geometria diferencial abstrata
• Análise em fractais

Ver também

• Geometria Discreta e Computacional (journal)
• Matemática discreta
• Paul Erdős

Referências

• Bezdek, András (2003). Discrete geometry: in honor of W. Kuperberg's 60th birthday. Marcel Dekker. New York, N.Y: [s.n.] ISBN 0-8247-0968-3 
• Bezdek, Károly (2010). Classical Topics in Discrete Geometry. Springer. New York, N.Y: [s.n.] ISBN 978-1-4419-0599-4 
• Bezdek, Károly (2013). Lectures on Sphere Arrangements - the Discrete Geometric Side. Springer. New York, N.Y: [s.n.] ISBN 978-1-4614-8117-1 
• Bezdek, Károly; Deza, Antoine; Ye, Yinyu (2013). Discrete Geometry and Optimization. Springer. New York, N.Y: [s.n.] ISBN 978-3-319-00200-2 
• Brass, Peter; Moser, William; Pach, János (2005). Research problems in discrete geometry. Springer. Berlin: [s.n.] ISBN 0-387-23815-8 
• Pach, János; Agarwal, Pankaj K. (1995). Combinatorial geometry. Wiley-Interscience. New York: [s.n.] ISBN 0-471-58890-3 
• Goodman, Jacob E. and O'Rourke, Joseph (2004). Handbook of Discrete and Computational Geometry, Second Edition. Chapman & Hall/CRC. Boca Raton: [s.n.] ISBN 1-58488-301-4  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Gruber, Peter M. (2007). Convex and Discrete Geometry. Springer. Berlin: [s.n.] ISBN 3-540-71132-5. [Peter M. Gruber Resumo divulgativo] 
• Matoušek, Jiří (2002). Lectures on discrete geometry. Springer. Berlin: [s.n.] ISBN 0-387-95374-4 
• Vladimir Boltyanski, Horst Martini, Petru S. Soltan (1997). Excursions into Combinatorial Geometry. Springer. [S.l.: s.n.] ISBN 3-540-61341-2  !CS1 manut: Nomes múltiplos: lista de autores (link)