4
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ I'm unsure how to tag this. Glad for any advice. $\endgroup$
    – Josephine
    Commented Oct 19, 2011 at 12:02
  • 1
    $\begingroup$ You are misusing the term "fewnomial" here: fewnomials refer to polynomials which have arbitrarily high degree, but the number of monomials is independent on that degree. Here, you have only degree 2... $\endgroup$
    – Thierry Zell
    Commented Oct 19, 2011 at 15:09
  • $\begingroup$ It looks like you have it already: compute differences, take dot products, pay attention to signs. Unless the constraints fit some pattern like disjoint triples, I don't see any nonobvious parallelization or other optimizations. Gerhard "Ask Me About System Design" Paseman, 2011.10.19 $\endgroup$
    – Gerhard Paseman
    Commented Oct 19, 2011 at 15:32
  • $\begingroup$ I expect that there is a polynomial-time (polynomial number of real arithmetic operations) algorithms to do this, but I don't really have time to dot all the i's and cross all the t's right now. But what I have in mind is not easily implemented or available as a black-box, so it depends on if you actually want to use such an algorithm, or simply know it exists. $\endgroup$
    – Thierry Zell
    Commented Oct 19, 2011 at 15:38
  • $\begingroup$ @Thierry Zell: Interesting. I was not able to find a definition of the term fewnomial. All i could find, was theorems that state that the number of nondegenerate roots of a polynomial does not depend on the degree of the polynomial. I don't understand the definition you give above. How can the number of monomials of a polynomial be dependent on the degree of the polynomial? $\endgroup$
    – Josephine
    Commented Oct 20, 2011 at 13:36

1 Answer 1

Reset to default
5
$\begingroup$

I believe your problem is NP-hard. If you had, not just triples-constraints for some triples, but had given the orientation of every triple, then you have specified what is known as the combinatorial order type of the point configuration. (See Handbook of Discrete and Computational Geometry, Chapter 5, "Pseudoline arrangements.") This is equivalent (in some sense) to a rank-3 oriented matroid. It is NP-hard to determine whether or not an oriented matroid is realizable by points in $\mathbb{R}^2$. This was established in a 1991 paper by Peter Shor, "Stretchability of pseudolines is NP-hard" (PDF link). Jürgen Richter-Gebert's Ph.D. thesis was on this topic: "On the realizability problem of combinatorial geometries—Decision methods," 1992.

Update. To respond to the request for more specific information, let me suggest Günter Ziegler's 1996 article, "Oriented Matroids Today" (PDF link), Section 3.4, "Realization algorithms," where he says,

the most efficient algorithm (in practice) currently available to find a realization (if one exists) is the iterative “rubber band” algorithm described in Pock [532].

As you can infer from the number 532, this article has a comprehensive bibliography!

I might also recommend looking at Aichholzer et al.'s 2001 paper, "Enumerating Order Types for Small Point Sets with Applications," which includes a clear exposition of the relationship between order types and pseudoline arrangements. Oswin Aichholzer maintains a very nice Order Type web page, which is worth visiting for the latest information. There you will learn that there are exactly 2,334,512,907 order types of 11-point sets.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the references! In this handbook Richter-Gebert gives the complexity for the best know algorithm to decide the realizability of a given oriented matroid. But he does not give the actual algorithm. And i cannot find it in the handbook. Do you have any suggestion where i could find a description of that algorithm or any other good algorithm for that problem? $\endgroup$
    – Josephine
    Commented Oct 20, 2011 at 13:08
  • $\begingroup$ I've now added some more information. Perhaps start at Aichholzer's Order Type web page, which is quite current, and work chronologically backward. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 20, 2011 at 14:54
  • 1
    $\begingroup$ I was not able to get a copy of the thesis of Pock. I even asked at the University on which it was written. Does anyone know a source for it? $\endgroup$
    – Josephine
    Commented Mar 20, 2014 at 20:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .