3
$\begingroup$

We have $n$ points $P$ in $2D$ space. We want to find an enclosing equilateral triangle $\Delta$ with minimum area in $O(n\log n)$. Suppose We know that at least on side of $\Delta$ covers at least two points of $P$.

My first attempt: I try to compute convex hull of points, then I select three points of the hull and construct a triangle with minimum area, touching these points. The running time becomes $O(n^3)$ because we need to check each combination of three points from $O(n)$ points - so it's inefficient.

Second try: I think this problem have is related with lover envelope, but I can't formulate it in dual manner. Any help to solve this problem in $O(n\log n)$ will be appreciated.

$\endgroup$
1
2
$\begingroup$

Let’s consider the following problem at first – given a convex polygon $H = (v_1,v_2,...,v_m)$ and a direction (unit vector) $\vec a$, find a farthest vertex $v \in H$ along this direction (it will be a vertex with maximum value of the dot product $\vec a \cdot \vec v$). Obviously, this problem can be solved by brute force in $O(m)$ time.

If the polygon is static and the query direction varies, then it makes sense to preprocess the polygon to answer this query faster. For each vertex $v \in H$ we can calculate a range of directions (a wedge), for which this vertex will be the farthest one - please see the picture below.

PolygonWithWedges

It’s easy to see, that wedges for two vertices, connected by an edge, have a common side – and this side is exactly the outward-pointing normal for this edge. These wedges together with corresponding vertices can be stored in a tree-like data structure. So, for any given direction we’ll be able to use this structure to find a wedge, containing this direction, and also the farthest vertex, corresponding to this wedge, in $O(\log m)$ time.

Returning to the main problem – we need at first to compute the convex hull $H$ for the set $P$, and then to preprocess the polygon $H$ as described above. After that we can scan edges of the polygon one by one, constructing the minimal enclosing equilateral triangle for each edge and recording its minimum area. For each edge the line, collinear with this edge, defines the direction of the first side of the triangle – and this side will contain two polygon vertices. As soon as the direction of the first side is known we can find directions (normal vectors) for other two sides by rotating it by $120^o$ and $240^o$. Then we use the tree, described above, to find farthest vertices for the second and third side of the triangle.

The convex hull computation plus the polygon preprocessing takes $O(n \log n)$ time. The loop over polygon edges takes $m \le n$ steps, and on each step we need to do two binary searches with depth $O(\log m)$, so the overall time will be $O(n \log n)$.

$\endgroup$
3
  • $\begingroup$ While it seems somewhat intuitive that the triangle must contains an edge of the convex hull, I can't find a way to prove it formally. Could you give a sketch of proof? $\endgroup$ – Nathaniel Apr 8 at 23:45
  • $\begingroup$ @Nathaniel - sorry to say, no... however this requirement is in the OP question $\endgroup$ – HEKTO Apr 8 at 23:47
  • $\begingroup$ Oh, I missed that fact, thanks for pointing it out. $\endgroup$ – Nathaniel Apr 8 at 23:49

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.