Real Algebraic and Analytic Geometry |

An Algorithm for convexity of semilinear sets over ordered fields.

e-mail: , ,

Submission: 2006, January 31.

*Abstract:
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