research-article

On Symmetry Detection

Author:

M. J. AtallahAuthors Info & Claims

IEEE Transactions on Computers, Volume 34, Issue 7

Pages 663 - 666

https://doi.org/10.1109/TC.1985.1676605

Published: 01 July 1985 Publication History

Publisher Site

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 O(n log n) time lower bound for this problem.

Cited By

View all

De Luca FHossain MKobourov S(2019)Symmetry Detection and Classification in Drawings of GraphsGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_38(499-513)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_38
Gnutti AGuerrini FLeonardi R(2017)On Reflection Symmetry In Natural ImagesProceedings of the 15th International Workshop on Content-Based Multimedia Indexing10.1145/3095713.3095743(1-7)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3095713.3095743
Korman SLitman RAvidan SBronstein A(2015)Probably Approximately SymmetricComputer Graphics Forum10.1111/cgf.1245434:1(2-13)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1111/cgf.12454
Show More Cited By

Index Terms

On Symmetry Detection
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Index terms have been assigned to the content through auto-classification.

Recommendations

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
Abstract
We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of Ω(n²), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a ...
Read More
An optimal algorithm for constructing an optimal bridge between two simple rectilinear polygons

Let P and Q be two disjoint rectilinear polygons in the plane. We say P and Q are in Case 1 if there exists a rectinlinear line segment to connect them; otherwise, we say they are in Case 2. In this paper, we present optimal algorithms for solving the ...
Read More
Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane

We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O ( n log ^3/2 n ) time and O ( n log n )...
Read More

Comments

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 34, Issue 7

July 1985

101 pages

ISSN:0018-9340

Editor:
T. Feng

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 July 1985

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Other Metrics

View Author Metrics

Citations

Cited By

View all

De Luca FHossain MKobourov S(2019)Symmetry Detection and Classification in Drawings of GraphsGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_38(499-513)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_38
Gnutti AGuerrini FLeonardi R(2017)On Reflection Symmetry In Natural ImagesProceedings of the 15th International Workshop on Content-Based Multimedia Indexing10.1145/3095713.3095743(1-7)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3095713.3095743
Korman SLitman RAvidan SBronstein A(2015)Probably Approximately SymmetricComputer Graphics Forum10.1111/cgf.1245434:1(2-13)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1111/cgf.12454
Micheal AVani KSanjeevi S(2014)Automatic detection of ridges in lunar images using phase symmetry and phase congruencyComputers & Geosciences10.1016/j.cageo.2014.09.00573:C(122-131)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.cageo.2014.09.005
Mitra NPauly MWand MCeylan D(2013)Symmetry in 3D GeometryComputer Graphics Forum10.1111/cgf.1201032:6(1-23)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1111/cgf.12010
Zingoni A(2012)Symmetry recognition in group-theoretic computational schemes for complex structural systemsComputers and Structures10.5555/2799694.279988294:C(34-44)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.5555/2799694.2799882
Kindalov MBogdanova AErakovic ZIvanović MBudimac Z(2012)A novel algorithm for an image processing system in entomologyProceedings of the Fifth Balkan Conference in Informatics10.1145/2371316.2371318(1-7)Online publication date: 16-Sep-2012
https://dl.acm.org/doi/10.1145/2371316.2371318
Murali VBirchfield S(2012)Autonomous exploration using rapid perception of low-resolution image informationAutonomous Robots10.1007/s10514-011-9262-z32:2(115-128)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s10514-011-9262-z
Cullen BO'Sullivan CCunningham DIsenberg T(2011)Symmetry hybridsProceedings of the International Symposium on Computational Aesthetics in Graphics, Visualization, and Imaging10.1145/2030441.2030448(33-38)Online publication date: 5-Aug-2011
https://dl.acm.org/doi/10.1145/2030441.2030448
Hooda ABronstein MBronstein AHoraud R(2011)Shape palindromesProceedings of the Third international conference on Scale Space and Variational Methods in Computer Vision10.1007/978-3-642-24785-9_56(665-676)Online publication date: 29-May-2011
https://dl.acm.org/doi/10.1007/978-3-642-24785-9_56
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

An optimal algorithm for constructing an optimal bridge between two simple rectilinear polygons

Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations