<p>Let <span class="math-container">$(x_1, y_1), ..., (x_k, y_k)$</span> be <span class="math-container">$n$</span> points in <span class="math-container">$\Re^2$</span>. For my sake, <span class="math-container">$k=20$</span>.</p>
<p>I am trying to set up a linear program to find a set of <span class="math-container">$k$</span> points in the plane <span class="math-container">$P$</span> that satisfy some linear constraints <span class="math-container">$\mathcal{C}(x_1, ..., x_k, y_1, ..., y_k)$</span>. I can do this by just setting up a linear program.</p>
<p>However, I want the resulting set of points <span class="math-container">$P$</span> to be in general position (i.e no <span class="math-container">$3$</span> lie on the same line). Is there a way to enforce the general position constraint on the points using linear constraints ?</p>

CC BY-SA 4.0
2023-11-24T02:08:11.880Z
I believe all sets with three colinear points have size 0, so if you just randomly adjust the output it should be valid with probability 1
Command Master
CC BY-SA 4.0
2023-11-25T23:55:09.597Z
@a3nm, those are not linear equations, so such a system of equations can't be solved using linear programming.  In particular, you can't use $\ne$ in a linear program.  I encourage you to use Latex/Mathjax to format formulas.
D.W.
CC BY-SA 4.0
2023-11-25T23:57:03.993Z
@CommandMaster, a linear programming solver does not output random points.  It outputs points in a systematic way.  How do you know that there is a probability 1 of its output being in general position?  That doesn't seem guaranteed.  Indeed, for some linear systems, all valid solutions will have 3 points in a line, so the probability that the output of the linear solver is valid might be 0.  Randomly modifying the values produced by the linear program is not guaranteed to work as there is no guarantee it still satisfies the linear constraints after the random modification.
D.W.
CC BY-SA 4.0
2023-11-26T03:41:06.563Z
@D.W.: Ah, yes, of course. I guess I must have assumed the coordinates of the points were already known, but that's silly.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-11-26T04:19:24.053Z
@D.W. I meant that if the equalities don't force collinearity, then if you take an optimal solution and add some arbitrarily small random value to it (while preserving its validity) then it will not have colinear points with probability 1
Command Master
CC BY-SA 4.0
2023-11-26T04:22:42.693Z
@CommandMaster, I don't think you have understood my point, and I don't think you've responded to it.  Adding a small random value does not necessarily preserve validity.  Just putting a parenthetical "while preserving its validity" does not make it so.  You have not described how to add a random value while preserving validity.  That might be very hard.  If you believe you have an answer, please write it in the Your Answer box, not in the comment box, but I continue to maintain that there are major gaps in your proposed approach that I don't think are easy to address.
D.W.
CC BY-SA 4.0
2023-11-26T05:56:31.957Z
@D.W. The idea is that if you look at the simplex described by the linear program, its solution will be one of its vertices, say $v$, and if the edges near that point are $e_1, e_2, ..., e_n$, and $x_1, x_2, ..., x_n \leq \frac1n$ then from convexity $v + x_1e_1 + x_2e_2 + \cdots + x_ne_n$ is valid, and if $x_1, x_2, ..., x_n$ are random and there exists a solution with no colinear points then (this is the part I'm not sure about, but I think it can be proved with algebraic geometry) with probability 1 $v + x_1e_1 + x_2e_2 + \cdots + x_ne_n$ will be one.
Command Master
CC BY-SA 4.0
2023-11-26T06:19:27.493Z
@CommandMaster, I believe that argument has a major gap and it is not at all clear to me whether it can be proven to work.  If you want to answer the question, the best way is to write an answer in the 'Your Answer' box, and make explicit the justification that it works in all cases, including a proof that the solution output by a LP solver is "random" and a proof that the probability for that particular method of constructing a point is 1.  Answering the question in the comments is discouraged on Stack Exchange sites.
D.W.
CC BY-SA 4.0
2023-11-28T13:24:39.273Z
Intuitively this doesn't seem possible to me (in a generic way). The feasible set of a LP is connected, while the set of points in $\mathbb{R}^{2n}$ corresponding to $n$ points in general position has $2^{\Theta(n\log n)}$ connected components. You can't express falling in this set as a LP.
Tassle
<computational-geometry><convex-geometry>
Enforcing general position in $2d$ linear programming
user3508551
# Enforcing general position in $2d$ linear programming

(Asked by: username_0 on 2023-11-23)

Let $(x\_1, y\_1), ..., (x\_k, y\_k)$ be $n$ points in $\Re^2$. For my sake, $k=20$.

I am trying to set up a linear program to find a set of $k$ points in the plane $P$ that satisfy some linear constraints $\mathcal{C}(x\_1, ..., x\_k, y\_1, ..., y\_k)$. I can do this by just setting up a linear program.

However, I want the resulting set of points $P$ to be in general position (i.e no $3$ lie on the same line). Is there a way to enforce the general position constraint on the points using linear constraints ?

**Tags:** computational-geometry, convex-geometry

> **Comments:**
> **username_1**: I believe all sets with three colinear points have size 0, so if you just randomly adjust the output it should be valid with probability 1  
> **username_2**: @a3nm, those are not linear equations, so such a system of equations can't be solved using linear programming.  In particular, you can't use $\ne$ in a linear program.  I encourage you to use Latex/Mathjax to format formulas.  
> **username_2**: @CommandMaster, a linear programming solver does not output random points.  It outputs points in a systematic way.  How do you know that there is a probability 1 of its output being in general position?  That doesn't seem guaranteed.  Indeed, for some linear systems, all valid solutions will have 3 points in a line, so the probability that the output of the linear solver is valid might be 0.  Randomly modifying the values produced by the linear program is not guaranteed to work as there is no guarantee it still satisfies the linear constraints after the random modification.  
> **username_3**: @username_2: Ah, yes, of course. I guess I must have assumed the coordinates of the points were already known, but that's silly.  
> **username_1**: @username_2 I meant that if the equalities don't force collinearity, then if you take an optimal solution and add some arbitrarily small random value to it (while preserving its validity) then it will not have colinear points with probability 1  
> **username_2**: @CommandMaster, I don't think you have understood my point, and I don't think you've responded to it.  Adding a small random value does not necessarily preserve validity.  Just putting a parenthetical "while preserving its validity" does not make it so.  You have not described how to add a random value while preserving validity.  That might be very hard.  If you believe you have an answer, please write it in the Your Answer box, not in the comment box, but I continue to maintain that there are major gaps in your proposed approach that I don't think are easy to address.  
> **username_1**: @username_2 The idea is that if you look at the simplex described by the linear program, its solution will be one of its vertices, say $v$, and if the edges near that point are $e_1, e_2, ..., e_n$, and $x_1, x_2, ..., x_n \leq \frac1n$ then from convexity $v + x_1e_1 + x_2e_2 + \cdots + x_ne_n$ is valid, and if $x_1, x_2, ..., x_n$ are random and there exists a solution with no colinear points then (this is the part I'm not sure about, but I think it can be proved with algebraic geometry) with probability 1 $v + x_1e_1 + x_2e_2 + \cdots + x_ne_n$ will be one.  
> **username_2**: @CommandMaster, I believe that argument has a major gap and it is not at all clear to me whether it can be proven to work.  If you want to answer the question, the best way is to write an answer in the 'Your Answer' box, and make explicit the justification that it works in all cases, including a proof that the solution output by a LP solver is "random" and a proof that the probability for that particular method of constructing a point is 1.  Answering the question in the comments is discouraged on Stack Exchange sites.  
> **username_4**: Intuitively this doesn't seem possible to me (in a generic way). The feasible set of a LP is connected, while the set of points in $\mathbb{R}^{2n}$ corresponding to $n$ points in general position has $2^{\Theta(n\log n)}$ connected components. You can't express falling in this set as a LP.  

---

## 0 answers

