2
$\begingroup$

My question is very similar to another solved question. As the title indicates, the major difference in my question is that I need to find the convex polygon that encloses the maximum number of points with a given area (instead of finding the circle that encloses the maximum number of points with a given radius).

So my question is as the following:

Given $n$ points $p_1,\dots,p_n$ in the plane and an area $A$, find a convex polygon $\mathcal{P}$ whose area is $\le A$ and that contains as many of the $n$ points as possible.

I already checked on the Minimum bounding box algorithms and Convex hull algorithms. I also found some implementations for Minimum bounding polygon. However, those previous algorithms don't consider the concept of determining the convex polygon that encloses as many points as possible of a given set of points and a given area. Finally I invented an approach to solve the problem but it doesn't work in some cases.

The idea of my approach is to start by finding the minimum bounding box for all the points. If the resulting polygon's area is greater than the given area, I cut off one of the edge points according to some technique, then I re-compute the minimum bounding box and test the area. I keep looping until I reach the desired area. I won't get into details with my approach as it's not working properly.

EDIT

As a simplified solution, finding any rectangle (it doesn't have to be axis-aligned) that encloses the maximum number of points with a given area would be very beneficial and works as a temporary solution for my problem.

$\endgroup$
  • $\begingroup$ Are you looking for a pragmatic solution that might work OK in practice (or as well as can be done), or are you looking for a theoretical result on the worst-case complexity of this problem? $\endgroup$ – D.W. Mar 2 '14 at 19:34
4
$\begingroup$

It sounds like your problem is the following:

Given $n$ points $p_1,\dots,p_n$ in the plane and an area $A$, find a polygon $\mathcal{P}$ whose area is $\le A$ and that contains as many of the $n$ points as possible.

This problem looks pretty tough to me, and I don't have a great algorithm for it, but I'll suggest two schemes. The first solves a simplified version of this problem (for rectangles instead of arbitrary polygons), and the second is a heuristic algorithm that might or might not work "well enough" on real-world instances.

Simplified variant: rectangles

Suppose we focus on the easier case where $\mathcal{P}$ must be an axis-aligned rectangle. Then I can give a $O(n^2 (\lg n)^2)$ time algorithm.

Without loss of generality, the $x$-coordinate of the left and right sides of this rectangle must agree with the $x$-coordinate of some pair of points, and similarly for the top and bottom sides.

So, guess the $x$-coordinate of the left side of the rectangle (there are $\le n$ possibilities), say $x_L$. Now, do a binary search on the width of the rectangle (there are $\le n$ possibilities), using the following ideas.

Given a guess at the width $w$ of the rectangle, you can calculate the maximum number of points that can fit in an allowable rectangle with those $x$-coordinates for the left and right sides, as follows. Start by filtering out all points whose $x$-coordinate is not in $[x_L,x_L+w]$. Sort the remaining points by their $y$-axis. Now look for the $y$-value $y_B$ for the bottom side of the rectangle, which maximizes the number of remaining points whose $y$-coordinate is in the range $[y_B,y_B+A/w]$. This can be found with a straightforward linear scan of the remaining points (with two pointers advancing monotonically).

With this, given $x_L$, you can do a binary search for $w$. Each guess at $w$ takes $O(n \lg n)$ work to compute the maximum number of points that can be fit into a rectangle of that sort. Since there are $\le n$ possible values for $w$, you'll do $O(\lg n)$ iterations in the binary search. Since there are $\le n$ possibilities for $x_L$, the overall running time is $O(n^2 (\lg n)^2)$.

Since a rectangle is a convex polygon, this gives you a lower bound on the number of points that can be covered by a convex polygon with area $\le A$. It might not be an especially tight lower bound, but maybe it's a start.

Heuristic for arbitrary polygons

We could use branch-and-bound type techniques here.

Define a directed acyclic graph (dag), the search dag, where each vertex is a convex polyhedron $\mathcal{P}$ obtained as the convex hull of some subset of the $n$ points, and there is an edge from $\mathcal{P}$ to $\mathcal{Q}$ if there is some point $p_i$ not in $\mathcal{P}$ such that the convex hull of $\mathcal{P},p_i$ is $\mathcal{Q}$. The root of this graph is the empty polyhedron, which covers no points. Call any node of this graph that has no out-edges a "leaf". The best polyhedron must be some leaf.

A naive approach would be to do a breadth-first search on this dag. Unfortunately, the dag is probably exponential in size, so this naive approach will probably be too slow.

You might do better using branch-and-bound techniques. Define the "quality" of a leaf in this graph to be the number of points covered by its associated polyhedron. Also, define the "quality" of a node $x$ in this graph to be the maximum of the quality of all of the leaves that are reachable from $x$. Of course, we cannot compute the quality of a node without exploring everything reachable from it (which is too expensive), but we can estimate it.

In particular, we can compute an upper bound on the quality of any given node. This is enough to do branch-and-bound. We basically iteratively explore the graph. At each stage, we keep track of the "best" solution we've found so far: i.e., among all the polyhedron $\mathcal{P}$ corresponding to some node we've visited, keep track of the maximum number of points covered by any of these. Say this number is $b$. Now if we reach a node $x$ where our upper bound on its quality implies that the quality of $x$ is $\le b$, then we don't need to visit $x$ or any of its descendants. This might help us reduce the search space.

How do we get an upper bound on the quality of a node? Well, here's one way. Suppose we have precomputed, for each $i=1,2,\dots,k$, the minimal area of any convex polygon that contains $i$ points, call it $\alpha(i)$. Now if we have a node $x$ that corresponds to a polyhedron $\mathcal{P}_x$ of area $A_x$, and if $A_x+\alpha(i) > A$, then here's an upper bound on the quality of $\mathcal{P}$: it must be at most the number of points contained in $\mathcal{P}$, plus $i-1$. This could be a somewhat loose bound, but it is something.

How do we do the precomputation? Well, that's basically an easier instance of the same problem, with a smaller value for $A$. So, we can do the precomputation via a recursive or iterative application of this algorithm, for increasing values of $A$ (or via similar ideas).

$\endgroup$
  • $\begingroup$ Thank you, I'll dig into your answer hoping to come up with an algorithm with an acceptable complexity. $\endgroup$ – yazanpro Mar 3 '14 at 20:19

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.