Minimum area triangle from a given set of points

views:

answers:

+3 Q:

Minimum area triangle from a given set of points

Given a set of n points, can we find three points that describe a triangle with minimum area in O(n^2)? If yes, how, and if not, can we do better than O(n^3)?

I have found some papers that state that this problem is at least as hard as the problem that asks to find three collinear points (a triangle with area 0). These papers describe an O(n^2) solution to this problem by reducing it to an instance of the 3-sum problem. I couldn't find any solution for what I'm interested in however. See this (look for General Position) for such a paper and more information on 3-sum.

+2 A:

There's an algorithm that finds the required area with complexity O(n^2*log(n)).

For each point Pi in set do the following(without loss of generality we can assume that Pi is in the origin or translate the points to make it so).

Then for each points (x1,y1), (x2,y2) the triangle area will be 0.5*|x1*y2-x2*y1| so we need to minimize that value. Instead of iterating through all pairs of remaining points (which gives us O(N^3) complexity) we sort those points using predicate X1 * Y2 < X2 * Y1. It is claimed that to find triangle with minimal area we need to check only the pairs of adjacent points in the sorted array.

So the complexity of this procedure for each point is n*log(n) and the whole algorithm works in O(n^2*log(n))

P.S. Can't quickly find the proof that this algorithm is correct :(, hope will find it it later and post it then.

Vladimir 2010-10-15 09:38:17

Can you please elaborate a bit? Why is the triangle area `0.5|x1*y2 - x2*y1|`? This comes from a determinant if I'm not mistaken, but it won't give you the triangle area as it only uses two points instead of three. Also, why are you sorting for each point when it looks like each sort will be the same? And finally, you don't seem to include `Pi` anywhere in your algorithm; what role does each `Pi` play?

IVlad 2010-10-15 10:03:14

@IVlad I think, for each point PI he converts every point (x, y) into (x - PI.x, y - PI.y). (thus, moving PI itself into coordinate origin) Algorithm looks plausible.

Nikita Rybak 2010-10-15 10:13:26

@Nikita Rybak - oh, right, he did say translate the points. +1, looks good.

IVlad 2010-10-15 10:19:49

@IVlad I've read about this algorithm recently and also found its implementation in internet (http://www.opita.net/node/402 - in russian) but could not find the proof yet

Vladimir 2010-10-15 10:32:40

Looking at it again, there's a problem. Let's say, PI is (0, 0) and there're 3 more points: A(100, 100), B(2, 1), C(1, 2). It's clear that points B and C should be used, but sorted order will be B, A, C.

Nikita Rybak 2010-10-15 10:41:52

indeed... may be it is implied that after iterating that way through all n points we will find the solution and the value on each particular iteration may be incorrect... need to think about it

Vladimir 2010-10-15 10:51:31

@Nikita Rybak - I haven't checked, but are you sure that when `Pi` becomes `B` or `C` the correct solution won't be found?

IVlad 2010-10-15 17:47:54

@IVlad No. Just my original impression was that algorithm attempts to locate optimal solution for every given PI (until I looked at it closer). If that's not the case, proof is even more necessary.

Nikita Rybak 2010-10-15 18:03:59

@IVlad Although, I think we can extend last example. Imagine small perfect triangle inside a large perfect triangle. (Or you can take a hexagon of perfect shape and increase one of its two base triangles without moving it.) Then we get the situation above for every vertex of the small triangle.

Nikita Rybak 2010-10-15 18:06:47

+3 A:

There are O(n^2) algorithms for finding the minimum area triangle.

For instance you can find one here: http://www.cs.tufts.edu/comp/163/fall09/CG-lecture9-LA.pdf

If I understood that pdf correctly:

The basic idea is as follows:

1) For each pair of points AB you find the point that is closest to it.

2) You construct a dual of the points so that lines <-> points. Line y = mx + c is mapped to point (m,c)

3) In the dual, for a given point (which corresponds to a segment in original set of points) the nearest line vertically gives us the required point for 1.

Apparently 2&3 can be done in O(n^2) time.

Also I doubt the papers showed 3SUM-hardness by reducing to 3SUM. It should be the other way round.

Moron 2010-10-15 14:02:46

The paper I linked to seems to reduce to 3-sum. They reduce the problem to finding 3 values `a b c` such that `a + b + c = 0`. +1, will have to read carefully to understand. I'll accept a bit later if no one comes up with something better.

IVlad 2010-10-15 18:00:32

ansaurus

tags:

views:

answers:

Minimum area triangle from a given set of points

related questions