Check if a polygon has an axis of symmetry in $O(n)$ time 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?
 A: 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

