0
$\begingroup$

Let $T$ be a hexagonal tiling of the plane and assume we are given a simple polygon $P$ (we define $P$ as the union of the points on its boundary and its interior). The task is to find the subset of $T$ that intersects $P$ as fast as possible.

We can assume that the diameter of the hexagons are some fixed constant $c$, and that $c$ is proportional to the area or perimeter of $P$ if this makes things easier.

For instance, is it possible to derive an algorithm that does this in time polynomial in the perimeter or area of $P$?

I previously posted this on Math.SE, and received the following comment from Cheerful Parsnip:

One idea: first find a single hexagon that meets the polygon. Then do breadth first search on the set of adjacent hexagons to keep enlarging the set of hexagons that meet the polygon.

However the complexity (and correctness) of doing so is not clear to me.

$\endgroup$
6
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/4507256/14578, cs.stackexchange.com/q/153452/755. Please do not post the same question on multiple sites. If you realize you have posted on the wrong site, please edit your question to reflect the feedback and comments you've received, then delete it from the original site before posting elsewhere. $\endgroup$
    – D.W.
    Aug 6, 2022 at 19:17
  • $\begingroup$ Perhaps you could pick one site where you want this to appear and let us know which you have in mind. I notice that having it cross-posted has already caused some fragmentation: comments there aren't visible here, and the edit made on Math.SE isn't reflect here. Thanks! $\endgroup$
    – D.W.
    Aug 6, 2022 at 19:17
  • $\begingroup$ I’m voting to close this question because it was cross-posted. $\endgroup$
    – D.W.
    Aug 6, 2022 at 19:18
  • $\begingroup$ Absolutely. I was not aware of this rule, although it makes sense. Given the comments on MATH.SE it seems like a bad idea to close it on here. I'll instead delete it on MATH.SE if it gets reopened on here. I stated the comments from MATH.SE in the bottom of my question here (although do you mean something different? Refering to your comment on the MATH.SE site) so I do not think the "fragmentation" would cause confusion. $\endgroup$
    – GeomA
    Aug 6, 2022 at 19:20
  • $\begingroup$ I don't think deleting the copy on Math.SE is a good idea because it will lose the detailed suggestions you got there (the summary in the question here is not a substitute for the details there, as the summary in the question here is much vaguer), so if you'd like it to appear here, I suggest editing the question to explain the algorithm that was proposed there and to capture the edits/improvements that were made there first. $\endgroup$
    – D.W.
    Aug 6, 2022 at 19:24

2 Answers 2

1
$\begingroup$

Checking if two polygons intersect is equivalent to checking if a point lies inside their Minkwoski sum. Illustration with a triangle: enter image description here

The Minkowki sum of a polygon and a convex hexagon is found in linear time in the number of vertices (see http://acg.cs.tau.ac.il/courses/algorithmic-robotics/spring-2011/slides/ms.pdf, slide 16).

Now the problem is reduced to finding all points of a regular grid that fall inside a polygon. You can do that by triangulating the polygon, in time $O(n\log n)$ by sweepline (in theory $O(n)$ is possible for a simple polygon, but not in practice).

Then finding the range of grid lines that cross a triangle is done in constant time, these lines are enumerated in time equal to their number (triangle height over grid spacing), and the internal grid points are enumerated in time equal to their number (triangle area over grid cell area).

$\endgroup$
0
$\begingroup$

Yes, you can do it in approximately $O(\mathcal{A} + \mathcal{P} + n \log n)$ time, where $\mathcal{A}$ is the area of $P$, $\mathcal{P}$ is the perimeter of $P$, and $n$ is the number of vertices, using a sweep-line algorithm.

Sweep a vertical line, from left to to right. We have an event at each vertex of $P$ and at every $c/2$ units (representing the centers of the hexagons). At each time instant, the vertical sweepline is somewhere, and we keep track of all edges or vertices of $P$ that intersect the sweepline, stored in sorted order based on their $y$-coordinate. Assuming we're given all of the vertices of $P$ in sort order around its perimeter, it is easy to maintain the sweepline at each step. Now whenever the sweepline touches the center of hexagons, it is easy to enumerate all hexagons that intersect $P$ and intersect the sweepline.

If you store the edges/vertices that intersect the sweepline in a self-balancing binary tree, you can update them in $O(\log n)$ time each time the sweep line advances to a new vertex of $P$; and in each step, you can enumerate the hexagons that intersect $P$ and the sweepline in time linear in the number of such hexagons. The total number of hexagons that are outputted by this algorithm is linear in $\mathcal{A}+\mathcal{P}$, so the total running time is $O(\mathcal{A}+\mathcal{P} + n \log n)$.

There might be ways to do it in linear time (e.g., using polynomial triangulation or something). I am not sure.

$\endgroup$
2
  • $\begingroup$ What are you assuming about $c$ here? Surely you cannot make something that is polynomial in just the area of the polygon. Consider a rectangle of width $1/n$ and height $n$. Your proposed algorithm will output something polynomial in the perimeter. $\endgroup$
    – sn3jd3r
    Aug 11, 2022 at 17:17
  • $\begingroup$ @sn3jd3r, you are quite right. Thank you for catching my error. Please see the updated answer. Does this look right to you? In particular, my claim is that for any fixed constant $c$, the total number of hexagons to output is $O(\mathcal{A}+\mathcal{P})$. $\endgroup$
    – D.W.
    Aug 12, 2022 at 7:28

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.