3
$\begingroup$

Suppose a convex polygon $P$ in plane is given. We want to triangulate it such that any arbitrary line $L$ intersects with $O(\log n)$ triangles.

I divide $P$ in half using a diagonal line. Then I continue in each half in the same way. But at this step I get stuck.

$\endgroup$
3
  • 1
    $\begingroup$ I'm not sure if your approach is the best way. Maybe a better idea is to ignore the triangles for a moment, and think about how the structure would look like if the line can only intersect $O(\log n)$ triangles or edges. Since we need it to be small independent of the direction, it seems you should make concentric "rings" with the same shape as the convex polygon, which decrease in size until the central ring is a triangle. To show that this structure has a "depth" of $O(\log n)$, look at the dual of the triangulation. $\endgroup$
    – Discrete lizard
    Feb 2, 2022 at 16:56
  • $\begingroup$ Can you explain more about your idea in as an answer? Thank you. $\endgroup$
    – er3
    Feb 2, 2022 at 17:13
  • 1
    $\begingroup$ I think it is better if you think about it on your own, and perhaps update your question if you hit some barrier. $\endgroup$
    – Discrete lizard
    Feb 2, 2022 at 19:46

1 Answer 1

3
$\begingroup$

Let the polygon be defined by the vertices in clockwise order: $(v_1, \dotsc, v_n)$. For simplicity, assume that $n$ is even.

  1. Add the lines: $(v_1,v_3)$, $(v_3,v_5)$,...,$(v_{n-2},v_1)$.
  2. Then, recursively triangulate the polygon: $(v_1, v_3, \dotsc, v_{n-2})$.

Note that, the algorithm creates $n/2$ triangles in step $1$. And, any arbitrary line $L$ can intersect at most $2$ of these triangles. By induction, it is easy to prove that any line $L$ will not intersect more than $2 \log n$ triangles overall.

$\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.