On Symmetry Detection
- 1 July 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (7) , 663-666
- https://doi.org/10.1109/tc.1985.1676605
Abstract
A straight line is an axis ofsymmetry of a planar figure if the figure is invariant to reflection with respect to that line. The purpose of this correspondence is to describe an O( n log n) time algorithm for enumerating all the axes of symmetry of a planar figure which is made up of (possibly intersecting) segments, circles, points, etc. The solution involves a reduction of the problem to a combinatorial question on words. Our algorithm is optimal since we can establish an Ω(n log n) time lower bound for this problem.Keywords
This publication has 2 references indexed in Scilit:
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- On the Optimality of Some Set AlgorithmsJournal of the ACM, 1972