Can we find the largest intersecting subfamily of convex polygons in quadratic time?

Question

Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (you can assume general position, no two vertices are the same, no edges intersects a vertex other than its endpoints, no three edges intersect at the same point).

I'm curious to know if you can you compute a subfamily of largest cardinality possible such that all polygons share a single common intersection point in $\mathcal{O}(n^2)$ time? (In the Real RAM model, i.e. you can store an arbitrary precision real number in a register and perform arithmetic operations on them in constant time)

The best I've managed to come up with is $\mathcal{O}(n^2\log(n))$:

• I can modify the Bentley-Ottman algorithm (with the segments being the polygon edges) so that at every event point $p$, I count the number of "lower hull" edges and "upper hull" edges under $p$ on the sweep line (modifying my search tree so this can be done in $\mathcal{O}(\log(n))$ time) and compute the difference, giving me the number of polygons containing $p$. I simply keep track of the "best" point $p$, then test every polygon against $p$ in $\mathcal{O}(n)$ total time.

Alternatively, by computing the $\mathcal{O}(m^2)$ points which are the leftmost in the intersection of a pair of polygons (which can be shown to be doable in $\mathcal{O}(nm)$ time) and then counting the total number of polygons which contains each point (in $\mathcal{O}(nm^2)$ time), you can solve the problem in $\mathcal{O}(nm^2)$ time, which is better for small $m$ (and you can probably also get $\mathcal{O}(n^\alpha m^\beta)$ for different values of $\alpha + \beta > 2$ using more sophisticated simplex range counting datastructures).

Is anything faster possible (asymptotically)? Or is there some (conditional) lower bound showing that $\mathcal{O}(n^2)$ is hard/impossible to achieve?

Answer 1

As Discrete lizard pointed out in a comment, I misinterpreted the statement of "sharing a common point", which I read as "pairwise sharing a common point".

You can thus ignore the below answer. I will delete it later.

---

I'm not an expert in this area but I do actually believe that the problem you are talking about is surprisingly enough NP-complete.

The problem, known as Maximum Clique in convex planar sets (graph class: Conv) was proved NP-hard by Kratochvíl and Kuběna [1] who write the following:

We show that complements of planar graphs have intersection representations by convex sets in the plane, i.e., for every planar graph, one can assign convex sets in the plane to its vertices in such a way that two of the sets are disjoint if and only if the correspondning vertices are adjacent. This fact has a complexity consequence — it follows that the problem of determining the clique number of an intersection graph of convex sets in the plane is NP-hard. We note that the complexity of this problem for intersection graphs of straight line segments in the plane is unknown.

[1] Kratochvíl, Jan, and Aleš Kuběna. "On intersection representations of co-planar graphs." Discrete Mathematics 178.1-3 (1998): 251-255