# Partitioning a set of 2d polygons into intersection-connected subsets

My question is given a set of 2d polygons how can I find the connected components of polygons according to a criteria based on intersection or proximity of them.

In other words I have a set of polygons. I want to group them into subsets where each polygon has at least one intersection with (one or more) other polygon(s) of the subset and no intersections with any other polygon in a different subset. So if I have S = {A, B, C, D} and A intersects C and C intersects D the resulting partitions are: P1 = {A, C, D} and P2 = {B}.

I don't have any problems with an good approximate solution if its fast and doesn't generate false negatives (i.e. no (potential) intersection is lost).

I don't need to actually calculate the intersections just determine if they intersect.

In my case the polygons are complex but if a known answer only works for concave or simple polygons I would still like to know about it!

I am actually not sure how to phrase this question which may account for my lack of findings of relevant papers.

• In other words, you want to determine which polygons contribute to each component of the union. – Jeffε Jan 14 '14 at 21:12
• Yes that would be another way of putting it. – Juan Besa Jan 15 '14 at 14:28
• Are you looking for the complexity of the problem, or an actual algorithm to implement? – John Jan 16 '14 at 17:31
• I am looking for an algorithm to actually implement. Of course knowing if there is actually any possibility of an algorithm also helps! – Juan Besa Jan 22 '14 at 13:05

What you want is to find the connected components of the intersection graph of the polygons, right? It would help to be more clear about what counts as an intersection: do the boundaries have to cross or does one polygon entirely inside another count as an intersection? And can the polygons have holes?

Regardless, a natural lower bound for running times for the problem is $\Omega(n^{4/3})$ where $n$ is the total number of segments in the input. Any faster and we could also improve the known time bounds for Hopcroft's problem of detecting an intersection between $n$ given points and $n$ given lines: expand each point into a small polygon (not so large that it intersects any line it didn't before) and test whether any of these expanded points belongs to a nontrivial connected component. This lower bound is mentioned briefly in my paper "Testing Bipartiteness of Geometric Intersection Graphs" which uses it to argue that bipartiteness of intersection graphs is strictly easier than connectivity; it in turn cites Jeff Erickson's paper "New lower bounds for Hopcroft’s problem", which proves an $\Omega(n^{4/3})$ lower bound in a reasonable but limited model of computation.

• By intersection I would include a polygon inside of a polygon as an intersection. So in essence if they share at least one point in their interior or there boundaries cross its an intersection. – Juan Besa Jan 17 '14 at 14:53
• What about convex polygons? I bad approximation would be to use the convex hull of each polygon and obtaining that intersection graph of them. I am sure it can be done using just the bounding boxes as an even coarser approximation. – Juan Besa Jan 17 '14 at 14:57
• This lower bound applies directly to convex polygons: each line is convex by itself, and each point (or each small expansion of the point) is also convex. – David Eppstein Jan 17 '14 at 17:05

Make an undirected graph where each vertex corresponds to a polygon and link any pair of vertices if their corresponding polygons overlap. Then run whatever connected component labeling algorithm you like on the result.

To expand on Mikola's answer, you could modify a sweep-line algorithm like the Bentley-Ottman algorithm (http://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm) to detect the crossings, and maintain an auxiliary graph structure where each polygon is represented by a vertex. Mark each line segment with its polygon's representative graph vertex. Each time you detect a crossing between two line segments from different polygons, add an edge between the corresponding vertices of the auxiliary graph (if one does not already exist). In the end, the connected components of the auxiliary graph will give you exactly what you want.

• The problem with this approach is contained in Mr. Eppsteins answer. If a polygon is completely contained inside another polygon then no actual intersection between boundaries occurs and you would not detect come intersections between polygons. – Juan Besa Jan 17 '14 at 15:00
• Ah, sorry Juan. I didn't read carefully enough! I was thinking only of boundary intersections, not interior intersections. – John Feb 4 '14 at 20:39