Real Algebraic and Analytic Geometry

Preprint Server

Previous   Next
12. C. Andradas, R. Rubio, M.P. Vélez:
An Algorithm for convexity of semilinear sets over ordered fields.

e-mail: , ,

Submission: 2006, January 31.

In this paper we study semilinear sets over arbitrary ordered fields. In particular we show that open (resp. closed) semilinear sets are convex if and only if they are basic, that is, a finite intersection of open (resp. closed) halfspaces. As a corollary we get that any bounded convex closed semilinear set is the convex hull of a finite family of points and we obtain a separation result for convex closed semilinear sets.
We recover the constructive proof of these results to get an algorithm for convexity of these sets. This algorithm is polynomial in the number of variables and basic pieces of the initial description; but it is exponential in the number of linear functions which describe the set. An implementation of this method was made in the Computer Algebra System Maple 6. We finish with some examples of this implementation.

Mathematics Subject Classification (2000): 14P10, 52B55, 68W30.

Keywords and Phrases: semilinear sets, convexity, polyhedra, algorithm.

Full text, 17p.: dvi 101k, ps.gz 157k, pdf 210k.

Server Home Page