13
$\begingroup$

I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ contains all of the positive and none of the negative points; by assumption, the sample admits at least 1 consistent triangle).

The best they (or I) could do is an algorithm that runs in time $O(m^6)$, where $m$ is sample size. Can anyone do better?

$\endgroup$
  • $\begingroup$ Just to be clear: the vertices of the triangle do not need to be points of the collection, right? And it's acceptable to have negative points on the boundary? $\endgroup$ – ex0du5 May 31 '12 at 16:21
  • $\begingroup$ (1) I had voted to close the question because I had misunderstood the problem. The system does not allow me to cancel my vote, but I virtually cancel it. (2) I think that there is an O(m log m)-time algorithm, but do not have time to verify it right now. The idea is to compute the convex hull of the positive examples and to sweep around this convex hull to find three lines forming the desired triangle. $\endgroup$ – Tsuyoshi Ito May 31 '12 at 17:47
  • $\begingroup$ @ex0du5 -- indeed, the vertices of the triangle need not consist of the sample points. As for boundary issues, these can be ignored here as they are inessential. [If the boundary counts as part of the triangle, then you won't have negative points on the boundary.] $\endgroup$ – Aryeh May 31 '12 at 18:59
  • $\begingroup$ @TsuyoshiIto: I was thinking similarly, but there are cases where you cannot have the triangle edges be collinear to the edges of the convex hull, but a triangle still exists. The triangle still obviously contains the convex hull, but it's not just extending the lines of the hull and finding the triangle. You may need lines that are rotated around some of the vertices to avoid the negative points. That was why I asked about negatives on the boundary, to allow a search algorithm that chose lines from the vertices of the hull to negatives to keep it a discrete search. $\endgroup$ – ex0du5 May 31 '12 at 19:17
  • $\begingroup$ @ex0du5: Well, I did not assume that the edges of the triangle are parallel to some edges of the convex hull of the positive examples. $\endgroup$ – Tsuyoshi Ito May 31 '12 at 21:24
14
$\begingroup$

As @TsuyoshiIto suggests, there is an $O(n\log n)$-time algorithm for this problem, due to Edelsbrunner and Preparata. In fact, their algorithm finds a convex polygon with the minimum possible number of edges that separates the two point sets. They also prove an $\Omega(n\log n)$ lower bound for the more general problem in the algebraic decision tree model; however, it's not clear whether this lower bound applies to the triangle case.

A full description of the algorithm is too long to post here, but here's the basic idea. Let $C$ be the convex hull of the positive points. For each negative point $q$, consider the lines through $q$ that are tangent to $C$. These lines split the plane into four wedges, one of which contains $C$; let $W(q)$ be the wedge opposite the one that contains $C$. Finally, let $F$ (the "forbidden region") be the union of all wedges $W(q)$. Any separating triangle must separate $C$ from $F$. Both $C$ and $F$ can be constructed in $O(n\log n)$ time.

example of $C$ and $F$

Label the edges of $F$ alternately clockwise and counterclockwise. Edelsbrunner and Preparata further prove that if a separating triangle exists, then there is a separating triangle whose edges are collinear with clockwise edges of $F$. In $O(n)$ additional time, we can find the (necessarily clockwise) edge of $F$ first hit by a ray from each clockwise edge $e$; call this edge the "successor" of $e$. The successor pointers partition the clockwise edges into cycles; if there is a separating triangle, one of these successor cycles has length 3 (and none have length more than 4).

See the original paper for more details:

$\endgroup$
3
$\begingroup$

It seems to me that it is enough to consider tangent lines from the '-1' points onto the convex hull of the '+1' points as the candidates for the sides of $T$ (let's say that '+1' points will be inner to $T$).

Too bad, I can't publish images here. But picture this: $t$ is the tangent line to the convex hull that goes through some '-1' point. $A$ is the tangency point. $B$ is the extreme (see below) point on $t$, and $BC$ is the tangent line from the point $B$ ($C$ is the tangency point).

So, the algorithm is the following. For every line $t$ of the tangents lines we can try to build a triangle based on it:

  1. Compute the intersection points of $t$ with all the other lines;
  2. Find an extreme (farthest from $A$) point $B$ and the corresponding line $t'$ to the right (or left) from $A$, such that the psuedotriangle $ABC$ (=$AB$, $BC$ and the part of the convex hull between $A$ and $C$) doesn't contain '-1' points (i.e. doesn't contain any points).
  3. Do the same with the line $t'$ and see if we can 'close' the triangle.

It looks like this would be a $O(m^2)$ running time. Maybe this can be improved by using some data structures?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.