Bibliografische Daten exportieren
Literatur vom gleichen Autor
im Publikationsserver

# Konstruktion und Eigenschaften ganzzahliger Punktmengen

URN zum Zitieren dieses Dokuments: urn:nbn:de:bvb:703-opus-1933

## Titelangaben

Kurz, Sascha:
Konstruktion und Eigenschaften ganzzahliger Punktmengen.
Bayreuth , 2005
( Dissertation, 2005 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

## Volltext

An integral point set P is a set of n points in the m-dimensional Euclidean space E^m with pairwise integral distances. The largest distance of a point set P is called its diameter diam(P). From the combinatorial point of view there is a natural interest in the minimum diameter d(m,n) for given parameters m and n. An m-dimensional point set is in semi-general position if no m+1 points lie in an (m-1)-dimensional hyperplane. If additionally no m+2 points are situated on an (m-1)-dimensional hypersphere we say that the point set is in general position. We denote the minimum diameter of an m-dimensional integral point set in semi-general position consisting of n points by $\overline{d}(m,n)$ and of a point set in general position by $\dot{d}(m,n)$. The aim of this thesis is to determine exact values of d(m,n), $\overline{d}(m,n)$, and $\dot{d}(m,n)$ by exhaustive computer enumeration and to give a bit more theoretical insight into the structure of integral point sets. Most of our presented algorithmic techniques can be applied in general for the construction of discrete structures. Due to the Heronian formula $$A_\Delta=\frac{\sqrt{(a+b+c)(a+b-c)(a-b+c)(-a+b+c)}}{4}$$ for the area of a triangle with side lengths a, b, and c, one can uniquely (for $A_\Delta\neq 0$) write the area as $A_\Delta=q\sqrt{k}$ with a rational number q and a squarefree integer k. This value k is called the characteristic of a triangle. A long known theorem states that in a plane integral point set each non-degenerate triangle has the same characteristic. This is a crucial fact for an efficient generation of plane integral point sets. We generalize the definition of characteristic to m-dimensional simplices and prove the corresponding theorem. Our strategy to construct integral point sets consisting of n+1 points with the aid of a computer is to union two integral point sets consisting of n point with n-1 points in common. In this context we present a variation of Read's orderly generation algorithm and combine it with clique search. So far the minimum diameters d(2,n) of plane integral point sets have been known only for n<=9. We determine these values for n<=89. Here it turned out that plane integral point sets with minimum diameter d(2,n) for 9<=n<=89 consist of n-1 points situated on a line. We conjecture this pattern for n<= 9. For plane integral point sets P with $n^\varrho$ collinear points we prove $$diam(P)\ge n^{\frac{\varrho}{4\log 2(1+\varepsilon)} \log\log n}$$ for $\varepsilon>0$, $n\ge n_0(\varepsilon)$, and $0<\varrho<1$. The previously known bounds for the minimum diameter are $$c_1n<d(2,n)<n^{c_2\log\log n}$$ with suitable chosen constants $c_1$ and $c_2$. We present a possible strategy to prove $$n^{c_3\log\log n}<d(2,n)$$ and figure out some of the details. For plane integral point sets in semi-general position we extend the known values of $\overline{d}(2,n)$ from n<=9 to n<=36. In the 3-dimensional space we correct the value for d(3,9) given in the literature and determine d(3,n) in the range 11<=n<=23 and $\overline{d}(3,7)$ for the first time. We also give constructions which give good upper bounds for d(m,n) for arbitrary m and n. If n is small in comparison to m we give a construction showing d(m,n)<=17 for n<=m^2+m$. For d(m,m+1) only 3 or 4 is possible. So far d(m,m+1)=3 was shown only for m=3,6,8. We give examples for 8<=m<=24 and several other values of m. The generation of integral simplices is a first step for the generation of integral point sets. So we have enumerated several numbers$\alpha(m,d)\$ of m-dimensional integral simplices with diameter d. The development of a very fast canonicity check for 4x4-matrices made it possible to enumerate the 8.430.487.428.682 integral tetrahedrons with diameter 800 in less than 10 hours. A simple loop from 1 to this number would also last nearly 9 hours on the same computer. For integral simplices with diameter 2 we rediscover a bijection into the set of partitions of m+1. Searching for a generalization we examine integral simplices having at most 2 different distances and corresponding graph classes. For integral point sets having at most 2 distances n<=m+2 was shown. So far examples reaching the upper bound were only known for m=3,8. We give a construction for odd m<=3. We solve an open problem of a bulgarian group by giving an effective algorithm to decide whether an integral point sets can be extended by a point keeping the property of pairwise integral distances or not.