Discrete tomography on modules [Elektronische Ressource] : decomposition, separation, and uniqueness / Barbara Langfeld

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2008
• Nombre de lectures: 11
• Langue: English

Extrait

Technische Universit¨at Mu¨nchen
Zentrum Mathematik
Discrete Tomography on Modules:
Decomposition, Separation,
and Uniqueness
Barbara Langfeld
Vollst¨andiger Abdruck der von der Fakult¨at fu¨r Mathematik der Technischen
Universit¨at Mu¨nchen zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr.rer.nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof.Dr. Martin Brokate
Pru¨fer der Dissertation: 1. Univ.-Prof.Dr. Peter Gritzmann
2. Univ.-Prof.Dr. Martin Henk
Otto-von-Guericke-Universit¨at Magdeburg
3. Prof. Gabor T. Herman, Ph.D.
City University of New York, USA
Die Dissertation wurde am 28.08.2007 bei der Technischen Universit¨at Mu¨nchen
eingereicht und durch die Fakult¨at fu¨r Mathematik am 10.12.2007 angenommen.Fu¨r Aiso,
Milo,
Ulrich
und meine Eltern.iiAbstract
We study three basic questions of discrete tomography on modules: First, we charac-
terize under which conditions the complete tomographicgriddecomposes intofinitely
many translates of the underlying module. Second, we deal with a geometric separa-
tion problem that arises naturally in reconstructing quasicrystalline point sets from
X-ray data. We show how to solve the separation problem algorithmically in a semi-
algebraic setting. Finally, we study the problem of finding the minimal number of
points in a tomographic grid that have to be prescribed as (non-)positions so as to
guarantee a unique reconstruction of a given sample from the X-ray data. We prove
theNP-hardness of this problem and derive related uniqueness results for polytopes.
Zusammenfassung
Die Arbeit untersucht drei grundlegende Fragen der Diskreten Tomographie auf
Moduln. Im ersten Teil wird charakterisiert, unter welchen Bedingungen das
vollst¨andige tomographische Grid in endlich viele Translate des zu Grunde liegen-
den Moduls zerf¨allt. Im zweiten Teil wird ein geometrisches Separationsproblem
studiert, dasinnatu¨rlicherWeise beiderRekonstruktion quasikristalliner Punktmen-
gen aus X-Ray-Daten auftritt. Wir zeigen, wie sich das Separationsproblem in einem
semialgebraischen Kontext algorithmisch effizient l¨osen l¨asst. Im dritten Teil unter-
suchen wir das Problem, eine minimale Anzahl an Gridpunkten zu finden, sodass die
Fixierung dieser Punkte als (Nicht-)Positionen die eindeutige Rekonstruktion eines
gegebenen Musters aus den X-Ray-Daten garantiert. Wir beweisen die NP-Schwere
dieses Problems und leiten verwandte Eindeutigkeitsresultate fu¨r Polytope ab.
iiiivContents
Dedication i
Abstract, Zusammenfassung iii
List of Symbols vii
1 Introduction 1
1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Decomposition and separation . . . . . . . . . . . . . . . . . . 6
1.2.2 Revealing positions to guarantee uniqueness . . . . . . . . . . 10
1.3 Structure of the thesis and main results . . . . . . . . . . . . . . . . . 11
1.4 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Siegel Grids 15
2.1 The index of Siegel grids . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 The decomposition problem in the discrete tomography of quasicrystals 25
2.3 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 Separation with Semialgebraic Containers 35
3.1 Semialgebraic containers . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.1 Semialgebraic sets . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.2 Some facts about arrangements . . . . . . . . . . . . . . . . . 38
3.1.3 On the computation of Sep (P) with semialgebraic C . . . . . 40C
3.2 The number of operations needed to compute Sep (P) . . . . . . . . 44C
3.3 Consequences for the discrete tomography of quasicrystals . . . . . . 48
3.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4 Uniqueness Numbers of Polytopes 55
4.1 Uniqueness numbers: Notation and first results . . . . . . . . . . . . . 55
4.2 Hardness results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
v4.3 Discrete tomography polytopes . . . . . . . . . . . . . . . . . . . . . 66
4.4 Proof of Theorem 4.2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.5 Proof of Theorem 4.4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.6 Consequences for discrete tomography . . . . . . . . . . . . . . . . . 86
4.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
List of Figures 89
References 91
Index 103
viList of Symbols
Special sets
∅ the empty set
N,N the set ofthe naturalnumbers (excluding resp. including 0)0
Z the set of the integers
Z Galois field with p elements, p being a primep
Q,R,C the set ofthe rationalnumbers, the set ofthe real numbers,
the set of the complex numbers, respectively
[a,b],[a,b),(a,b],(a,b) the intervals{x∈ R : a≤x≤b},{x∈ R : a≤x<b},
{x∈R : a<x≤b}, and{x∈R : a<x<b}, respectively
Operations on sets, comparing sets
|A| cardinality of A
cl(A), int(A), bd(A) closure, interior, and boundary of A, respectively
conv(A) convex hull of A
A+B, a+B Minkowsky-sum{a+b : a∈ A,b∈ B} of A and B resp.
the Minkowsky-sum{a}+B
AB, aB, Ab the set{ab : a∈ A,b∈ B}, the set{a}B, and the set
A{b}, respectively;
se.g., for v∈R , vR=Rv is the line{λv : λ∈R}
A⊂B A is subset of B (not excluding equality)
Operations on numbers, comparing numbers
|a| absolute value of a
⌈a⌉,⌊a⌋ smallest integer greater or equal to a, largest integer less or
equal to a, respectively
sign(a) sign of a i.e., sign(a)= 0 if a = 0, sign(a) =1 if a>0, and
sign(a) =−1 if a<0
Qn
n! ‘n factorial’, defined as the number i
i=1
n ‘n choose k’, defined as the number n!/(k!(n−k)!)
k
maxA, minA greatest resp. smallest number in the set of numbers A
viiOperations on vectors and matrices
T Tv , A transpose of the vector v resp. the matrix A
lin(V), lin (V) Z-linear span of V i.e., all linear combinations of elementsZ
of V with coefficients from the field or module Z; if Z is a
field and clear from the context, it will be skipped in the
symbol
dim(V), dim (V) dimension of the K-vector space V; if the field K is clearK
from the context, it will be skipped in the symbol
ker(A) kernel of A i.e., kernel of the mapping x →Ax
⊥ ⊥V ,v orthogonal complement of the set of vectors V resp. of{v}
Miscellaneous
O,Θ,Ω Landau symbols
∧,∨,¬ logical ‘and’, ‘or’, and negation
K[x] the ring of polynomials with indeterminate x and coeffi-
cients from the fieldK
K[x ,...,x ] the ring of multivariate polynomials with indeterminates1 d
x ,...,x and coefficients from the fieldK1 d
viii