2
$\begingroup$

Given a set of irregular polygons with the same number of points, where $polygon_i$ is completely contained within the boundary of $polygon_{(i+1)} $.

I need to find a set of vertices (one vertex from each polygon) such that the pairwise distances between all of the points selected are maximized.

What kind of algorithm should I be looking at to solve this problem? The practical use case of this would be a case with 4-8 polygons with roughly 1000-3000 vertices each, I am looking for an approach that could work under these parameters, but am also interested in the classification of this problem from a theoretical perspective.

It seems like this is case of treating each point as the center of circle that is a member of an independent set in a geometric intersection graph, and then moving the points along the polygon boundary that they lie on such that the radius is maximized while keeping the set independant.

Potential Simplifications here are:

  • Each polygon has the same number of vertices.
  • All vertices of $polygon_i$ are contained entirely within the area of $polygon_{(i+1)} $
  • All polygons lie on the same 2D plane.
$\endgroup$
0

1 Answer 1

0
$\begingroup$

I don't know whether this problem is in P. Given the similarity to facility location problems, it smells like it might be NP-hard. However, I can suggest some candidate algorithms. They break down into two categories: algorithms to get the exact optimal solution, and heuristics to get a pretty-good solution that hopefully will be an approximation to the optimal (but no guarantees).

Exact algorithms

One approach is to convert to a decision problem, and then an algorithm for independent set. The decision problem is:

Given sets $S_1,\dots,S_k$ of points and a distance $d$, is there a way to choose one point from each set so that no two points are at distance $\le d$ from each other?

(Each $S_i$ represents the set of points in a single polygon.) Binary search over $d$ lets you convert any algorithm for the decision problem into an algorithm for your optimization problem.

Now form a graph $G=(V,E)$ where $V=S_1 \cup \dots \cup S_k$, and where you have an edge between every pair of points that are at distance $\le d$ from each other. You are looking for an independent set $v_1,\dots,v_k$ such that $v_i \in S_i$ for all $i$. There are many approaches for solving such a problem.

For instance, you can express it as a SAT instance, and feed the result into a SAT solver. You'll have one boolean variable $v$ for each $v \in V$; if $v$ is set to true, then that means you've included $v$ in your set. Now you have a bunch of clauses of the form $(\neg v \lor \neg w)$ for each pair $(v,w) \in E$, asserting that you don't pick any pair of vertices at distance $\le d$, as well as a clause for each set $S_i$ asserting that you pick exactly one element of $S_i$.

Or, you could express it as an integer linear programming instance, and feed the result into an ILP solver. You'll have one zero-one variable $v$ for each $v \in V$; add an inequality $v+w \le 1$ for each pair $(v,w) \in E$, along with an equality $x_1+x_2+\dots + x_j = 1$ where $S_1=\{x_1,\dots,x_j\}$ (and similarly for each $S_i$).

Or you could apply an approximation algorithm for independent set, such as the greedy algorithm based on selecting the minimum degree vertex at each step.

The graph $G$ is a geometric intersection graph, so you might be able to use algorithmic ideas customized for that kind of graph. You'd have to investigate them for yourself and see if they can be applied to your problem.

Heuristics

One heuristic is to use the Farthest Point First heuristic from clustering. You pick a point arbitrarily, then pick the point that is furthest from it, then pick a third point that is furthest from these two (maximizes the minimum-pairwise-distance), and repeat.

You'll need to adjust it to your setting, to make sure you don't pick two points from the same polygon. There are multiple ways to do that, but one simple one is: if you've already picked some subset of points, then discard any remaining ones that are from the same polygon as one of those, and only consider what's left as a candidate for your next point.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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