Skip to main content
MathOverflow

Return to Question

Considered NP-hardness.
Source Link
Josephine
Josephine
  • 191
  • 4

Background

Considering a set of points $(x_i, y_i)$ in $\mathbb R^2$ and constraints between some triples of them, which state, whether the three points of the triple are oriented clockwise (R), counter-clockwise (L) or collinear (I), we can translate this into a set of inequalities of the form

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 < 0$

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 > 0$

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 = 0$

for (R), (L) and (I) respectively, where the polynomials on the left-hand side are obtained from the determinant

$\det \begin{pmatrix} 1 & x_1 & y_1 \newline 1 & x_2 & y_2 \newline 1 & x_3 & y_3 \end{pmatrix} = \begin{pmatrix} x_2 - x_1 \newline y_2 - y_1 \end{pmatrix} \cdot \begin{pmatrix} y_3 - y_1 \newline x_1 - x_3 \end{pmatrix} $.

So the set of constraints is satisfiable iff the corresponding system of (in-)equalities is satisfiable. Although this problem is NP-hard, i am interested in the following:

What is a (relatively) fast way to decide satisfiability of such a system of (in-)equalities?

Kind regards.

Background

Considering a set of points $(x_i, y_i)$ in $\mathbb R^2$ and constraints between some triples of them, which state, whether the three points of the triple are oriented clockwise (R), counter-clockwise (L) or collinear (I), we can translate this into a set of inequalities of the form

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 < 0$

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 > 0$

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 = 0$

for (R), (L) and (I) respectively, where the polynomials on the left-hand side are obtained from the determinant

$\det \begin{pmatrix} 1 & x_1 & y_1 \newline 1 & x_2 & y_2 \newline 1 & x_3 & y_3 \end{pmatrix} = \begin{pmatrix} x_2 - x_1 \newline y_2 - y_1 \end{pmatrix} \cdot \begin{pmatrix} y_3 - y_1 \newline x_1 - x_3 \end{pmatrix} $.

So the set of constraints is satisfiable iff the corresponding system of (in-)equalities is satisfiable.

What is a fast way to decide satisfiability of such a system of (in-)equalities?

Kind regards.

Background

Considering a set of points $(x_i, y_i)$ in $\mathbb R^2$ and constraints between some triples of them, which state, whether the three points of the triple are oriented clockwise (R), counter-clockwise (L) or collinear (I), we can translate this into a set of inequalities of the form

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 < 0$

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 > 0$

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 = 0$

for (R), (L) and (I) respectively, where the polynomials on the left-hand side are obtained from the determinant

$\det \begin{pmatrix} 1 & x_1 & y_1 \newline 1 & x_2 & y_2 \newline 1 & x_3 & y_3 \end{pmatrix} = \begin{pmatrix} x_2 - x_1 \newline y_2 - y_1 \end{pmatrix} \cdot \begin{pmatrix} y_3 - y_1 \newline x_1 - x_3 \end{pmatrix} $.

So the set of constraints is satisfiable iff the corresponding system of (in-)equalities is satisfiable. Although this problem is NP-hard, i am interested in the following:

What is a (relatively) fast way to decide satisfiability of such a system of (in-)equalities?

Kind regards.

added tags
Link
Josephine
Josephine
  • 191
  • 4
Source Link
Josephine
Josephine
  • 191
  • 4

A fast way to decide satisfiability of a set of simple fewnomial inequalities?

Background

Considering a set of points $(x_i, y_i)$ in $\mathbb R^2$ and constraints between some triples of them, which state, whether the three points of the triple are oriented clockwise (R), counter-clockwise (L) or collinear (I), we can translate this into a set of inequalities of the form

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 < 0$

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 > 0$

$x_1 y_2 - x_1 y_3 - x_2 y_1 + x_2 y_3 + x_3 y_1 - x_3 y_2 = 0$

for (R), (L) and (I) respectively, where the polynomials on the left-hand side are obtained from the determinant

$\det \begin{pmatrix} 1 & x_1 & y_1 \newline 1 & x_2 & y_2 \newline 1 & x_3 & y_3 \end{pmatrix} = \begin{pmatrix} x_2 - x_1 \newline y_2 - y_1 \end{pmatrix} \cdot \begin{pmatrix} y_3 - y_1 \newline x_1 - x_3 \end{pmatrix} $.

So the set of constraints is satisfiable iff the corresponding system of (in-)equalities is satisfiable.

What is a fast way to decide satisfiability of such a system of (in-)equalities?

Kind regards.