Dyskretna geometria - Discrete geometry

Zbiór okręgów i odpowiadający im wykres dysku jednostkowego

Geometria dyskretna i geometria kombinatoryczna to gałęzie geometrii, które badają właściwości kombinatoryczne i metody konstrukcyjne dyskretnych obiektów geometrycznych. Większość pytań dotyczących geometrii dyskretnej dotyczy skończonych lub dyskretnych zbiorów podstawowych obiektów geometrycznych, takich jak punkty , linie , płaszczyzny , okręgi , kule , wielokąty i tak dalej. Przedmiot koncentruje się na właściwościach kombinatorycznych tych obiektów, takich jak sposób, w jaki się przecinają lub jak można je rozmieścić, aby pokryć większy obiekt.

Geometria dyskretna w dużym stopniu pokrywa się z geometrią wypukłą i geometrią obliczeniową i jest ściśle związana z takimi zagadnieniami, jak geometria skończona , optymalizacja kombinatoryczna , geometria cyfrowa , dyskretna geometria różniczkowa , teoria grafów geometrycznych , geometria toryczna i topologia kombinatoryczna .

Historia

Chociaż wielościany i teselacje były przez wiele lat badane przez ludzi takich jak Kepler i Cauchy , współczesna geometria dyskretna ma swoje początki pod koniec XIX wieku. Wczesne badane tematy to: gęstość upakowania okręgów według Thue , konfiguracje rzutowe według Reye'a i Steinitza , geometria liczb według Minkowskiego oraz kolorowanie map według Taita, Heawooda i Hadwigera .

László Fejes Tóth , HSM Coxeter i Paul Erdős położyli podwaliny pod geometrię dyskretną .

Tematy

Wielościany i wielościany

Polytope jest geometryczny o płaskich bokach, która występuje w każdej ogólnej liczbie wymiarów. Wielokąt jest Polytope w dwóch wymiarach, A wielościanu w trzech wymiarach, a więc wyższe od wymiarów (takie jak 4-Polytope w czterech wymiarów). Niektóre teorie dalej uogólniają ideę włączenia takich obiektów, jak politopy nieograniczone ( apeirotopy i teselacje ) oraz politopy abstrakcyjne .

Poniżej przedstawiono niektóre aspekty politopów badanych w geometrii dyskretnej:

• Kombinatoryka wielościenna
• Politopy kratowe
• Wielomiany Ehrharta
• Twierdzenie Picka
• Hipoteza Hirscha

Opakowania, wykładziny i płytki

Opakowania, pokrycia i kafelki to sposoby na rozmieszczenie jednolitych obiektów (zazwyczaj kół, kul lub płytek) w regularny sposób na powierzchni lub kolektorze .

Sfera pakowania jest układ non-nakładających się sfer obrębie zawierającej przestrzeni. Rozważane sfery mają zazwyczaj identyczne rozmiary, a przestrzeń jest zwykle trójwymiarową przestrzenią euklidesową . Jednak problemy z upakowaniem kul można uogólnić, aby uwzględnić nierówne kule, n- wymiarową przestrzeń euklidesową (gdzie problemem staje się upakowanie okręgu w dwóch wymiarach lub upakowanie hipersfery w wyższych wymiarach) lub przestrzenie nieeuklidesowe, takie jak przestrzeń hiperboliczna .

Tesselacji z płaskiej powierzchni jest płytki o powierzchni przy użyciu jednej lub większej ilości geometrycznych kształtów zwane płytki, bez pokrywania się z i bez przerw. W matematyce teselacje można uogólnić na wyższe wymiary.

Konkretne tematy w tym obszarze obejmują:

• Opakowania okrągłe
• Opakowania sferyczne
• Przypuszczenie Keplera
• Quasikryształy
• kafelki aperiodyczne
• Wykres okresowy
• Skończone zasady podziału

Sztywność i elastyczność konstrukcji

Wykresy są rysowane w postaci prętów połączonych obrotowymi zawiasami. Cyklu wykres C ₄ pokazana jako kwadrat mogą być przechylane przez niebieski siły do równoległoboku, jest więc elastyczna wykresu. K ₃ , narysowany jako trójkąt, nie może być zmieniony przez żadną siłę, która jest do niego przyłożona, więc jest to wykres sztywny.

Sztywność strukturalna to teoria kombinatoryczna służąca do przewidywania elastyczności zespołów utworzonych ze sztywnych ciał połączonych elastycznymi połączeniami lub zawiasami .

Tematy w tym obszarze obejmują:

• Twierdzenie Cauchy'ego
• Elastyczne wielościany

Struktury incydentów

Siedem punktów to elementy siedmiu linii w płaszczyźnie Fano , przykład struktury padania.

Struktury padania uogólniają płaszczyzny (takie jak płaszczyzny afiniczne , rzutowe i Möbiusa ), jak widać z ich definicji aksjomatycznych. Struktury incydentalne również uogólniają analogi o wyższych wymiarach, a struktury skończone są czasami nazywane skończonymi geometriami .

Formalnie struktura zapadalności jest potrójna

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

gdzie P jest zbiorem „punktów”, L jest zbiorem „linii” i jest relacją padania . Elementy nazywane są flagami. Gdyby ${\ Displaystyle I \ podseteq P \ razy L}$${\ Displaystyle I}$

${\displaystyle (p,l)\w ja}$

mówimy, że punkt p "leży na" linii . ${\displaystyle l}$

Tematy w tym obszarze obejmują:

• Konfiguracje
• Układy linii
• Układy hiperplanów
• Budynki

Matroidy zorientowane

Zorientowane matroid jest struktura matematyczny wyodrębniająca właściwości skierowanych wykresów i układy wektorów w przestrzeni wektorowej powyżej w dziedzinie uporządkowanej (zwłaszcza w przypadku częściowo uporządkowane przestrzeni wektorowej ). Dla porównania, zwykły (tj. niezorientowany) matroid abstrahuje własności zależności , które są wspólne zarówno dla grafów , które niekoniecznie są skierowane , jak i dla układów wektorów nad polami , które niekoniecznie są uporządkowane .

Teoria grafów geometrycznych

Geometryczny wykres jest wykres , w którym wierzchołki albo krawędzie są połączone z geometrycznych obiektów. Przykłady obejmują euklidesowe wykresy, 1- szkielet o bryły lub Polytope , wykresy dyskowego i wykresy widoczności .

Tematy w tym obszarze obejmują:

• Rysowanie wykresu
• Wykresy wielościenne
• Losowe wykresy geometryczne
• Diagramy Woronoja i triangulacje Delaunaya

Proste kompleksy

Symplicjalnego złożony jest topologiczna przestrzeni pewnego rodzaju, wykonana przez „sklejanie” punktów , odcinków , trójkąty i ich ń wymiarową odpowiedniki (patrz rysunek). Kompleksów symplicjalnych nie należy mylić z bardziej abstrakcyjnym pojęciem zbioru symplicjalnego, pojawiającym się we współczesnej teorii homotopii symplicjalnej. Czysto kombinatoryczny odpowiednik kompleksu symplicjalnego jest abstrakcyjnym kompleksem symplicjalnym . Zobacz także losowe kompleksy geometryczne .

Kombinatoryka topologiczna

Dziedzina topologii kombinatorycznej wykorzystywała w topologii koncepcje kombinatoryczne, które na początku XX wieku przekształciły się w dziedzinę topologii algebraicznej .

W 1978 roku sytuacja uległa odwróceniu – do rozwiązania problemu w kombinatoryce zastosowano metody z topologii algebraicznej – kiedy László Lovász udowodnił hipotezę Knesera , rozpoczynając w ten sposób nowe badania nad kombinatoryką topologiczną . Dowód Lovásza wykorzystywał twierdzenie Borsuka-Ulama i twierdzenie to zachowuje znaczącą rolę w tej nowej dziedzinie. Twierdzenie to ma wiele równoważnych wersji i analogów i zostało użyte w badaniu problemów sprawiedliwego podziału .

Tematy w tym obszarze obejmują:

• Lemat Spernera
• Regularne mapy

Kraty i grupy dyskretne

Grupa dyskretna to grupa G wyposażona w topologię dyskretną . W tej topologii G staje się grupą topologiczną . Dyskretnych podgrupa topologicznej grupie G jest podgrupa H którego względem topologii jest jeden dyskretny. Na przykład, liczb całkowitych , Z tworzą dyskretne podgrupę liczb rzeczywistych , R (o standardowej topologii metryczną ), ale liczby wymierne , P , nie.

Kraty w lokalnie zwartej grupie topologicznej jest dyskretna podgrupy o tej własności, że iloraz przestrzeń ma skończoną środka niezmienny . W szczególnym przypadku podgrup Rn ^{sprowadza się} to do zwykłego geometrycznego pojęcia sieci , a zarówno struktura algebraiczna sieci, jak i geometria całości wszystkich sieci są stosunkowo dobrze zrozumiane. Głębokie wyniki Borela , Harisha-Chandry , Mostowa , Tamagawy , MS Raghunathana , Margulisa , Zimmera uzyskane od lat pięćdziesiątych do siedemdziesiątych dostarczyły przykładów i uogólniły wiele teorii na temat ustawienia nilpotentnych grup Liego i półprostych grup algebraicznych nad ciałem lokalnym . W latach 90. Bass i Lubotzky zainicjowali badania sieci drzew , które pozostają aktywnym obszarem badań.

Tematy w tym obszarze obejmują:

• Grupy refleksyjne
• Grupy trójkątów

Geometria cyfrowa

Geometria cyfrowa zajmuje się zbiorami dyskretnymi (zwykle dyskretnymi zbiorami punktów ) uważanymi za zdigitalizowane modele lub obrazy obiektów w 2D lub 3D przestrzeni euklidesowej .

Mówiąc najprościej, digitalizacja polega na zastąpieniu obiektu dyskretnym zbiorem jego punktów. Obrazy, które widzimy na ekranie telewizora, ekranie rastrowym komputera lub w gazetach, są w rzeczywistości obrazami cyfrowymi .

Jej główne obszary zastosowań to grafika komputerowa i analiza obrazu .

Dyskretna geometria różniczkowa

Dyskretna geometria różniczkowa to nauka o dyskretnych odpowiednikach pojęć w geometrii różniczkowej . Zamiast gładkich krzywych i powierzchni istnieją wielokąty , siatki i simplicjalne kompleksy . Znajduje zastosowanie w badaniach grafiki komputerowej i kombinatoryki topologicznej .

Tematy w tym obszarze obejmują:

• Dyskretny operator Laplacea
• Dyskretny rachunek zewnętrzny
• Rachunek dyskretny
• Dyskretna teoria Morse'a
• Kombinatoryka topologiczna
• Analiza kształtu spektralnego
• Abstrakcyjna geometria różniczkowa
• Analiza na fraktalach

Zobacz też

• Geometria dyskretna i obliczeniowa (dziennik)
• Matematyka dyskretna
• Paul Erdős

Uwagi

Bibliografia

• Bezdek, Andras (2003). Geometria dyskretna: na cześć 60. urodzin W. Kuperberga . Nowy Jork, NY: Marcel Dekker. Numer ISBN 0-8247-0968-3.
• Bezdek, Karol (2010). Klasyczne tematy w geometrii dyskretnej . Nowy Jork, NY: Springer. Numer ISBN 978-1-4419-0599-4.
• Bezdek, Karol (2013). Wykłady na temat układów sferycznych – strona geometryczna dyskretna . Nowy Jork, NY: Springer. Numer ISBN 978-1-4614-8117-1.
• Bezdek, Karol ; Deza, Antoine; Ye, Yinyu (2013). Dyskretna geometria i optymalizacja . Nowy Jork, NY: Springer. Numer ISBN 978-3-319-00200-2.
• Mosiądz, Piotr; Moser, William; Pach, Janos (2005). Problemy badawcze w geometrii dyskretnej . Berlin: Springer. Numer ISBN 0-387-23815-8.
• Pach, Janos ; Agarwal, Pankaj K. (1995). Geometria kombinatoryczna . Nowy Jork: Wiley-Interscience. Numer ISBN 0-471-58890-3.
• Goodman, Jacob E. i O'Rourke, Joseph (2004). Podręcznik geometrii dyskretnej i obliczeniowej, wydanie drugie . Boca Raton: Chapman & Hall/CRC. Numer ISBN 1-58488-301-4.CS1 maint: wiele nazwisk: lista autorów ( link )
• Gruber, Peter M. (2007). Geometria wypukła i dyskretna . Berlin: Springer. Numer ISBN 978-3-540-71132-2.
• Matoušek, Jiří (2002). Wykłady z geometrii dyskretnej . Berlin: Springer. Numer ISBN 0-387-95374-4.
• Vladimir Boltyanski , Horst Martini , Petru S. Soltan (1997). Wycieczki do geometrii kombinatorycznej . Skoczek. Numer ISBN 3-540-61341-2.CS1 maint: wiele nazwisk: lista autorów ( link )