5
$\begingroup$

Question: Is it possible to check if an $n$-gon has an axis of symmetry in $O(n)$ time?

Note: An $O(n^2)$ algorithm is easy to see: it is easy to check if any given line is an axis of symmetry of the $n$-gon in $O(n)$ time and for any $n$-gon, there are only $2n$ lines that are candidates for being an axis of symmetry — the angular bisectors of the n angles and the perpendicular bisectors of the $n$ sides.

Further question: If an $n$-gon has more than one axis of symmetry, is there an $O(n)$ algorithm to find them all?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Only lines that contain the polygon's center of gravity qualify as a symmetry axis $\endgroup$
    – Manfred Weis
    Commented Mar 20, 2021 at 20:07
  • 1
    $\begingroup$ There is an old paper that likely answers your question, but I cannot access it: "Symmetry Finding Algorithms," Peter Eades, 1988, DOI. $\endgroup$
    – Joseph O'Rourke
    Commented Mar 20, 2021 at 22:04
  • $\begingroup$ Thanks for the pointer and the observation. $\endgroup$
    – Nandakumar R
    Commented Mar 23, 2021 at 5:34

1 Answer 1

Reset to default
9
$\begingroup$

Indeed that paper I cited in the comments describes how to determine all symmetries of a polygon $P$ in $O(n)$ time. The polygon is first translated so that its centroid is at the origin. Then a "representation" $L(P)$ of $P$ is constructed. $L$ is an $n$-tuple of pairs $(d_i,\alpha_i)$, where $d_i$ is the length of polygon edge $i$, and $\alpha_i = \theta_{i+1} - \theta_i$, where $\theta_i$ is the angle the edge makes with the positive $x$-axis. So $\alpha_i$ is essentially the angle between adjacent edges.

A rotation by $2 \pi/k$ about the origin induces a rotation of $L$. All matching rotations are found using the Knuth–Morris–Pratt linear-time string-matching algorithm. Reflective symmetries are found by equating reflections with reversal followed by rotation. Then again string-matching may be employed.

This algorithm finds all symmetries in $O(n)$ time. I believe the algorithm as described is due to Glenn Manacher.

Peter Eades, "Symmetry Finding Algorithms." Machine Intelligence and Pattern Recognition, North-Holland, Volume 6, 1988, Pages 41-51. DOI

Improve this answer
$\endgroup$
2
  • $\begingroup$ Just a note. The algorithm was originally published in the Visual Computer (1985) by Jan D. Walter, Tony C. Woo, Richard A. Voltz. The paper called "Optimal algorithms for symmetry detection in two and three dimensions". Also your plot of the algorithm lacks rotational symmetries evaluation (number k is taken from it) required for the symmetry axes finding. $\endgroup$
    – Denis Gladkiy
    Commented May 6, 2022 at 11:18
  • $\begingroup$ That paper is available at deepblue.lib.umich.edu/bitstream/handle/2027.42/8338/…. I found it rather hard to implement in Python but eventually got code loosely based on it to work. $\endgroup$
    – user258279
    Commented Sep 12, 2023 at 7:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .