Rekonstrukcja poliomin wypukłych

Wstęp

Tomografia komputerowa jest dziedziną zajmującą się rekonstrukcją obiektów, które są opisane tylko przez pewien zbiór swoich rzutów. W tomografii dyskretnej obiektem, który chcemy zrekonstruować jest skończony zbiór pól w dwu- lub trójwymiarowej kracie. Wszystkie wiadomości o danym zbiorze pól są dostępne tylko w postaci dyskretnych rzutów. W najprostszym przypadku, rzut skończonego zbioru S w kierunku u jest funkcją, której wartości opisują liczbę punktów zbioru na każdej linii równoległej do u lub liczbę punktów zbioru S należących do podprzestrzeni prostopadłej do u. Problemy dyskretnej tomografii komputerowej są również studiowane w kontekście przetwarzania obrazów i kompresji danych.

Ważnym podproblemem jest tutaj rekonstrukcja dyskretnych zbiorów dwuwymiarowych z ich rzutów ortogonalnych, to jest poziomego i pionowego. Dla większości klas takich zbiorów problem rekonstrukcji jest NP-zupełny. W tej pracy zajmujemy się opisem i analizą pewnej klasy zbiorów dyskretnych, dla których rekonstrukcja jest możliwa w czasie wielomianowym. Klasa ta to poliomina wypukłe, czyli spójne zbiory o ciągłych przekrojach ortogonalnych. Zajmujemy się rekonstrukcją takich zbiorów z rzutów dokładnych oraz rekonstrukcją z rzutów przybliżonych, gdzie rzuty dopuszczalnego rozwiązania mogą się różnić o określony błąd od podanych rzutów wejściowych. Podajemy też wielomianowy algorytm rekonstrukcji z rzutów dokładnych dla pewnej klasy poliomin trójwymiarowych. Jest to pierwszy algorytm wielomianowy dla zbiorów trójwymiarowych.

Rozprawa jest podzielona na sześć rozdziałów. Rozdział pierwszy zawiera przedstawienie problemu oraz przegląd dotychczas uzyskanych wyników. W rozdziale drugim ujęte zostały pewne właściwości poliomin wypukłych, przydatne do konstruowania algorytmów rekonstrukcji. Rozdział trzeci zawiera opis i analizę wielomianowego algorytmu rekonstrukcji dwuwymiarowych poliomin wypukłych z rzutów ortogonalnych. W rozdziale czwartym dostosowujemy i uogólniamy ten algorytm do pewnej klasy trójwymiarowych poliomin wypukłych. Przedostatni, piąty rozdział dotyczy rekonstrukcji dwuwymiarowych poliomin wypukłych z rzutów przybliżonych. Pokazujemy w nim, że problem rekonstrukcji dwuwymiarowych zbiorów z przybliżonych rzutów jest co najmniej tak trudny, jak rekonstrukcja z dokładnych rzutów, oraz podajemy wielomianowy algorytm rekonstrukcji dla poliomin wypukłych. Na koniec, w rozdziale szóstym, podajemy niektóre problemy otwarte, które wiążą się bezpośrednio z problemami rozważanymi w tej pracy.

Pełny tekst pracy.

Prezentacja z obrony.