4
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ The question is slightly ambiguous, but I believe finding the largest subfamily of convex polygons with a single common intersection point $p$ is meant in this question. At least, that is what the suggested $O(n^2\log n)$ sweep-line algorithm computes (which appears to be correct). This is not equivalent to the maximum clique problem on the intersection graph of convex polygons, which finds a largest subfamily where each pair of polygons has an intersection, but for which the intersection of all polygons in the family may be empty. $\endgroup$ – Discrete lizard Feb 9 at 8:10
  • $\begingroup$ @Discretelizard Ah, yes, I see now, sharing a common point. $\endgroup$ – Pål GD Feb 9 at 8:12
  • $\begingroup$ Sorry for the confusion! I'll add and emphasize "single common intersection point". Anyways, thanks for the attempt! $\endgroup$ – Tassle Feb 9 at 11:16

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.