Lista tematów kombinatorycznej geometrii obliczeniowej

Lista tematów kombinatorycznej geometrii obliczeniowej wylicza tematy geometrii obliczeniowej , która stawia problemy w kategoriach obiektów geometrycznych jako bytów dyskretnych , a zatem metodami ich rozwiązywania są głównie teorie i algorytmy o charakterze kombinatorycznym .

Zobacz Lista tematów numerycznej geometrii obliczeniowej, aby zapoznać się z innym rodzajem geometrii obliczeniowej, która zajmuje się obiektami geometrycznymi jako bytami ciągłymi i stosuje metody i algorytmy natury charakterystyczne dla analizy numerycznej .

Konstrukcja/reprezentacja

Operacje boolowskie na wielokątach
Wypukły kadłub
Układ hiperpłaszczyznowy
Dekompozycja wielokątów
- Triangulacja wielokątów
  - Minimalny rozkład wypukły
  - Minimalny problem pokrycia wypukłego ( NP-twardy )
  - Minimalny rozkład prostokątny
- Problemy z teselacją
Problemy z sekcją kształtu
Prosty szkielet
Problem z linią cięcia
Triangulacja
Diagram Woronoja

Ekstremalne kształty

Minimalna ramka ograniczająca ( Najmniejsza ramka otaczająca , Najmniejsza ramka ograniczająca )
- Przypadek 2-D: Najmniejszy prostokąt ograniczający ( Najmniejszy prostokąt otaczający )
- Istnieją dwa typowe warianty tego problemu.
  - W wielu dziedzinach grafiki komputerowej ramka ograniczająca (często w skrócie bbox) jest rozumiana jako najmniejsza ramka ograniczona bokami równoległymi do osi współrzędnych, która obejmuje przedmiotowe obiekty.
  - W innych zastosowaniach, takich jak pakowanie , problemem jest znalezienie najmniejszego pudełka, w którym przedmiot (lub przedmioty) może się zmieścić („zapakowany”). Tutaj pudełko może przyjąć dowolną orientację w stosunku do „zapakowanych” przedmiotów.
Najmniejsza sfera ograniczająca (Najmniejsza otaczająca sfera)
- Przypadek 2-D: Najmniejszy okrąg ograniczający
Największy pusty prostokąt ( Maksymalny pusty prostokąt )
Największa pusta kula
- przypadek 2-D: Maksymalne puste koło ( największe puste koło )