OPUS 4 Latest Documents RSS FeedLatest documents
http://opus4.kobv.de/opus4-ubbayreuth/index/index/
Tue, 15 Apr 2008 11:07:00 +0200Tue, 15 Apr 2008 11:07:00 +0200Integral point sets over Z_n^m
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/377
There are many papers studying properties of point sets in the Euclidean space or on integer grids, with pairwise integral or rational distances. In this article we consider the distances or coordinates of the point sets which instead of being integers are elements of Z_n, and study the properties of the resulting combinatorial structures.Axel Kohnert; Sascha Kurzpreprinthttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/377Tue, 15 Apr 2008 11:07:00 +0200On the minimum diameter of plane integral point sets
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/375
Since ancient times mathematicians consider geometrical objects with integral side lengths. We consider plane integral point sets P, which are sets of n points in the plane with pairwise integral distances where not all the points are collinear. The largest occurring distance is called its diameter. Naturally the question about the minimum possible diameter d(2,n) of a plane integral point set consisting of n points arises. We give some new exact values and describe state-of-the-art algorithms to obtain them. It turns out that plane integral point sets with minimum diameter consist very likely of subsets with many collinear points. For this special kind of point sets we prove a lower bound for d(2,n) achieving the known upper bound n^{c_2loglog n} up to a constant in the exponent.Sascha Kurz; Alfred Wassermannpreprinthttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/375Tue, 15 Apr 2008 11:01:24 +0200Lotsize optimization leading to a p-median problem with cardinalities
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/373
We consider the problem of approximating the branch and size dependent demand of a fashion discounter with many branches by a distributing process being based on the branch delivery restricted to integral multiples of lots from a small set of available lot-types. We propose a formalized model which arises from a practical cooperation with an industry partner. Besides an integer linear programming formulation and a primal heuristic for this problem we also consider a more abstract version which we relate to several other classical optimization problems like the p-median problem, the facility location problem or the matching problem.Constantin Gaul; Sascha Kurz; Jörg Rambaupreprinthttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/373Tue, 15 Apr 2008 10:55:26 +0200Inclusion-maximal integral point sets over finite fields
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/372
We consider integral point sets in affine planes over finite fields. Here an integral point set is a set of points in $GF(q)^2$ where the formally defined Euclidean distance of every pair of points is an element of $GF(q)$. From another point of view we consider point sets over $GF(q)^2$ with few and prescribed directions. So this is related to Redeis work. Another motivation comes from the field of ordinary integral point sets in Euclidean spaces. In this article we study the spectrum of integral point sets over $GF(q)^2$ which are maximal with respect to inclusion. We give some theoretical results, constructions, conjectures, and some numerical data.Michael Kiermaier; Sascha Kurzpreprinthttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/372Tue, 15 Apr 2008 10:52:18 +0200Integral point sets over finite fields
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/371
We consider point sets in the affine plane GF(q)^2 where each Euclidean distance of two points is an element of GF(q). These sets are called integral point sets and were originally defined in m-dimensional Euclidean spaces. We determine their maximal cardinality I(GF(q),2). For arbitrary commutative rings R instead of GF(q) or for further restrictions as no three points on a line or no four points on a circle we give partial results. Additionally we study the geometric structure of the examples with maximum cardinality.Sascha Kurzpreprinthttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/371Tue, 15 Apr 2008 10:50:28 +0200Enumeration of integral tetrahedra
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/367
We determine the numbers of integral tetrahedra with diameter d up to isomorphism for all d<=1000 via computer enumeration. Therefore we give an algorithm that enumerates the integral tetrahedra with diameter at most d in O(d^5) time and an algorithm that can check the canonicity of a given integral tetrahedron with at most 6 integer comparisons. For the number of isomorphism classes of integral 4x4 matrices with diameter d fulfilling the triangle inequalities we derive an exact formula.Sascha Kurzworkingpaperhttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/367Tue, 15 Apr 2008 10:37:27 +0200Convex hulls of polyominoes
http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/245
In this article we prove a conjecture of Bezdek, Brass, and Harborth concerning the maximum volume of the convex hull of any facet-to-facet connected system of $n$ unit hypercubes in $mathbb{R}^d$. For $d=2$ we enumerate the extremal polyominoes and determine the set of possible areas of the convex hull for each $n$.Sascha Kurzpreprinthttp://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/245Thu, 01 Mar 2007 12:38:38 +0100