Geometria discreta - Discrete geometry

Uma coleção de círculos e o gráfico do disco da unidade 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 das perguntas em geometria discreta envolvem finitos ou discretos conjuntos de objectos geométricas básicas, tais como pontos , linhas , aviões , círculos , esferas , polígonos , e assim por diante. O assunto enfoca as propriedades combinatórias desses objetos, como a forma como eles se cruzam ou como podem ser organizados para cobrir um objeto maior.

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

História

Embora poliedros e tesselações tenham sido estudados por muitos anos por pessoas como Kepler e Cauchy , a geometria discreta moderna teve suas origens no final do século XIX. Os primeiros tópicos estudados foram: a densidade dos pacotes de círculo por Thue , configurações projetivas por Reye e Steinitz , a geometria dos números por Minkowski e cores de mapas por 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 politopos

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

A seguir estão alguns dos aspectos de politopos estudados em geometria discreta:

• Combinação poliédrica
• Polopos reticulados
• Polinômios de Ehrhart
• Teorema de Pick
• Conjectura de Hirsch

Embalagens, coberturas e ladrilhos

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

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

A tesselação de uma superfície plana é o ladrilho de um plano usando uma ou mais formas geométricas, chamadas ladrilhos, sem sobreposições e sem lacunas. Em matemática , as tesselações podem ser generalizadas para dimensões superiores.

Tópicos específicos nesta área incluem:

• Embalagens circulares
• Embalagens de esfera
• Conjectura de Kepler
• Quasicristais
• Aperiódica
• Gráfico periódico
• Regras de subdivisão finitas

Rigidez estrutural e flexibilidade

Os gráficos são desenhados como hastes conectadas por dobradiças giratórias. O gráfico do ciclo C ₄ desenhado como um quadrado pode ser inclinado pela força azul em um paralelogramo, por isso é um gráfico flexível. K ₃ , desenhado como um triângulo, não pode ser alterado por nenhuma força aplicada a ele, 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
• Poliedros flexíveis

Estruturas de incidência

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

As estruturas de incidência generalizam planos (como 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 superiores e as estruturas finitas são algumas vezes chamadas de geometrias finitas .

Formalmente, uma estrutura de incidência é tripla

${\ displaystyle C = (P, L, I). \,}$

onde P é um conjunto de "pontos", L é um conjunto de "linhas" e é a relação de incidência . Os elementos de são chamados de bandeiras. Se ${\ displaystyle I \ subseteq P \ times L}$${\ displaystyle I}$

${\ displaystyle (p, l) \ in I,}$

dizemos que o ponto p "está" na linha . ${\ displaystyle l}$

Os tópicos nesta área incluem:

• Configurações
• Arranjos de linha
• Arranjos de hiperplano
• Edifícios

Matróides orientadas

Um matróide orientado é uma estrutura matemática que abstrai as propriedades de gráficos direcionados e de arranjos de vetores em um espaço vetorial sobre um campo ordenado (particularmente para espaços vetoriais parcialmente ordenados ). Em comparação, uma matróide comum (isto é, não orientada) abstrai as propriedades de dependência que são comuns tanto aos gráficos , que não são necessariamente direcionados , quanto aos arranjos de vetores sobre campos , que não são necessariamente ordenados .

Teoria dos grafos geométricos

Um gráfico geométrico é um gráfico no qual os vértices ou arestas estão associados a objetos geométricos . Os exemplos incluem gráficos euclidianos, o esqueleto 1 de um poliedro ou politopo , gráficos de disco unitário e gráficos de visibilidade .

Os tópicos nesta área incluem:

• Desenho gráfico
• Gráficos poliédricos
• Gráficos geométricos aleatórios
• 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 linha , triângulos e suas contrapartes n- dimensionais (veja a ilustração). Os complexos simplificados não devem ser confundidos com a noção mais abstrata de um conjunto simplicial que aparece na moderna teoria da homotopia simplicial. A contraparte puramente combinatória de um complexo simplicial é um complexo simplicial abstrato . Veja também complexos geométricos aleatórios .

Combinação topológica

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

Em 1978, a situação se inverteu - métodos da topologia algébrica foram usados ​​para resolver um problema de combinatória - quando László Lovász provou a conjectura de Kneser , iniciando assim o novo estudo da combinatória topológica . A prova de Lovász usou o teorema de Borsuk-Ulam e este teorema retém um papel proeminente neste novo campo. Este teorema tem muitas versões equivalentes e análogos e tem sido usado no estudo de problemas de divisão justa .

Os tópicos nesta área incluem:

• Lema de Sperner
• Mapas regulares

Treliças e grupos discretos

Um grupo discreto é um grupo G equipado com a topologia discreta . Com esta topologia, G torna-se um grupo topológico . Um subgrupo discreto de um grupo topológico G é um subgrupo H cuja topologia relativa é discreta. Por exemplo, os 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 rede em um grupo topológico localmente compacto é um subgrupo discreto com a propriedade de que o espaço quociente tem medida invariante finita . No caso especial de subgrupos de R ⁿ , isso equivale à noção geométrica usual de uma rede , e tanto a estrutura algébrica das redes quanto a geometria da totalidade de todas as redes são relativamente bem compreendidas. Resultados profundos de Borel , Harish-Chandra , Mostow , Tamagawa , MS Raghunathan , Margulis , Zimmer obtidos dos anos 1950 até os anos 1970 forneceram exemplos e generalizaram grande parte da teoria para a configuração de grupos de Lie nilpotentes e grupos algébricos semisimples sobre um campo local . Na década de 1990, Bass e Lubotzky iniciaram o estudo de treliças de árvores , que permanece 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, digitalizar é substituir um objeto por um conjunto discreto de seus pontos. As imagens que vemos na tela da TV, na exibição raster de um computador ou nos jornais são, na verdade, 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 . É usado no estudo de computação gráfica e combinatória topológica .

Os tópicos nesta área incluem:

• Operador discreto Laplace
• Cálculo exterior discreto
• Cálculo discreto
• Teoria de Morse discreta
• Combinação topológica
• Análise de forma espectral
• Geometria diferencial abstrata
• Análise em fractais

Veja também

• Geometria Discreta e Computacional (periódico)
• Matemática discreta
• Paul Erdős

Notas

Referências

• Bezdek, András (2003). Geometria discreta: em homenagem ao 60º aniversário de W. Kuperberg . New York, NY: Marcel Dekker. ISBN 0-8247-0968-3.
• Bezdek, Károly (2010). Tópicos Clássicos em Geometria Discreta . New York, NY: Springer. ISBN 978-1-4419-0599-4.
• Bezdek, Károly (2013). Aulas sobre arranjos de esferas - o lado geométrico discreto . New York, NY: Springer. ISBN 978-1-4614-8117-1.
• Bezdek, Károly ; Deza, Antoine; Sim, Yinyu (2013). Geometria Discreta e Otimização . New York, NY: Springer. ISBN 978-3-319-00200-2.
• Brass, Peter; Moser, William; Pach, János (2005). Problemas de pesquisa em geometria discreta . Berlim: Springer. ISBN 0-387-23815-8.
• Pach, János ; Agarwal, Pankaj K. (1995). Geometria combinatória . Nova York: Wiley-Interscience. ISBN 0-471-58890-3.
• Goodman, Jacob E. e O'Rourke, Joseph (2004). Handbook of Discrete and Computational Geometry, Second Edition . Boca Raton: Chapman & Hall / CRC. ISBN 1-58488-301-4.CS1 maint: vários nomes: lista de autores ( link )
• Gruber, Peter M. (2007). Geometria Convexa e Discreta . Berlim: Springer. ISBN 978-3-540-71132-2.
• Matoušek, Jiří (2002). Aulas de geometria discreta . Berlim: Springer. ISBN 0-387-95374-4.
• Vladimir Boltyanski , Horst Martini , Petru S. Soltan (1997). Excursões em geometria combinatória . Springer. ISBN 3-540-61341-2.CS1 maint: vários nomes: lista de autores ( link )