Solving a LP feasibility using CGAL

Question

Can we solve linear programming feasibility problem of form mentioned below using CGAL(if not, please suggest alternatives):

v.x_a > c and,

v.x_b = c

where v,x_a,x_b,c are vector, vector, vector and scalar respectively. I want to find a tuple (v,c) for a given set of x( x_a and x_b are elements of x) which satisfies this inequality.

I have seen the documentation but allowable form is of type Ax(relation operator)b where relation operator can be >=,<= or =, where both A and b are known and x is unknown but my requirement is opposite, that is I have x but I want to determine if there exists a tuple (A,b) which satisfies the inequality.

Context: I am trying to implement a 3D mesh generator for which I need to test whether an edge(joins two 3D vertices) is Delaunay. Delaunay edge is defined as: An edge is Delaunay, iff there exists a circumsphere of its endpoints not containing any other vertex inside it.

My question is based on the approach described here

Answer 1

According to the construction that David Eppstein describes in the linked question, i and j are fixed and we have the additional restriction that v.xi = v.xj = c. So the problem becomes:

Find a vector v != 0 such that v.xk >= v.xi for all k and v.xi = v.xj.

This can be transformed to

Find a vector v != 0 such that (xk - xi).v >= 0 for all k and (xi - xj).v >= 0 and -(xi - xj).v >= 0

By defining A as the matrix with rows xk - xi for all k, xi - xj and xj - xi, we get

Find a vector v != 0 such that Av >= 0

which has the form you need. You can enforce the v != 0 by brute-forcing the non-zero component. For each component i and, trying adding the condition vi >= 1 or vi <= -1 and check the resulting system for solvability. Since the normal vector of the plane can be scaled arbitrarily, there is a solution iif any of the resulting programs is solvable (there are 2d of them if d is the dimensionality of v).