| Abstract | The relatively recent theory of sparse variable elimination exploits the structure in polynomial equations in order to define tighter bounds on the number of common roots and faster methods for numerically approximating them. The model of sparsity is of combinatorial nature, which leads naturally to certain problems in convex geometry in general dimensional euclidean spaces. This work addresses one such problem, namely the computation of certain 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. Output-sensitive bounds are derived for our algorithm, in terms of the sparsity parameters of the problem. A public domain implementation is described and its performance illustrated on certain families of inputs. |
