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 ?

  • $\begingroup$ 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 $\endgroup$ Commented Nov 24, 2023 at 2:08
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented Nov 25, 2023 at 23:55
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented Nov 25, 2023 at 23:57
  • $\begingroup$ @D.W.: Ah, yes, of course. I guess I must have assumed the coordinates of the points were already known, but that's silly. $\endgroup$
    – a3nm
    Commented Nov 26, 2023 at 3:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Commented Nov 28, 2023 at 13:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.