Details:
Title  Enumerating a subset of the integer points inside a Minkowski sum  Author(s)  Ioannis Z. Emiris  Type  Technical Report, Misc  Abstract  The relatively recent theory of sparse variable elimination exploits the structure of algebraic equations in order to relate it, on the one hand, to the bounds on the number of roots and, on the other, to the complexity of numerically approximating all of them. The model of sparsity is of combinatorial nature, which leads naturally to certain problems in convex geometry in generaldimensional euclidean spaces. This work addresses one such problem, namely the computation of a certain subset of integer points in the interior of integer convex polytopes. These polytopes are Minkowski sums, but avoiding their explicit construction is precisely one of the main features of the algorithm. Complexity bounds for our algorithm are derived under mild hypotheses, in terms of outputsize and in terms of the sparsity parameters of the input system. A public domain implementation is described and its performance illustrated on certain families of inputs. Experiments are also used to confirm the asymptotic behaviour of practical complexity. Linear programming lies at the inner loop of the algorithm, which explains why the structure of the respective problems is analyzed and comparative experiments are conducted with different implementations. 
URL 
http://cgi.di.uoa.gr/~emiris/indexeng.html 
Language  English  Year  2000  Month  July  Edition  0  Translation 
No  Refereed 
No 
