Axiality (geometry)

In the geometry of the Euclidean plane, axiality is a measure of how much axial symmetry a shape has. It is defined as the ratio of areas of the largest axially symmetric subset of the shape to the whole shape. Equivalently it is the largest fraction of the area of the shape that can be covered by a mirror reflection of the shape (with any orientation).

A shape that is itself axially symmetric, such as an isosceles triangle, will have an axiality of exactly one, whereas an asymmetric shape, such as a scalene triangle, will have axiality less than one.

Upper and lower bounds

Lassak (2002) showed that every convex set has axiality at least 2/3.[1] This result improved a previous lower bound of 5/8 by Krakowski (1963).[2] The best upper bound known is given by a particular convex quadrilateral, found through a computer search, whose axiality is less than 0.816.[3]

For triangles and for centrally symmetric convex bodies, the axiality is always somewhat higher: every triangle, and every centrally symmetric convex body, has axiality at least . In the set of obtuse triangles whose vertices have -coordinates , , and , the axiality approaches in the limit as the -coordinates approach zero, showing that the lower bound is as large as possible. It is also possible to construct a sequence of centrally symmetric parallelograms whose axiality has the same limit, again showing that the lower bound is tight.[4][5]

Algorithms

The axiality of a given convex shape can be approximated arbitrarily closely in sublinear time, given access to the shape by oracles for finding an extreme point in a given direction and for finding the intersection of the shape with a line.[6]

Barequet & Rogol (2007) consider the problem of computing the axiality exactly, for both convex and non-convex polygons. The set of all possible reflection symmetry lines in the plane is (by projective duality) a two-dimensional space, which they partition into cells within which the pattern of crossings of the polygon with its reflection is fixed, causing the axiality to vary smoothly within each cell. They thus reduce the problem to a numerical computation within each cell, which they do not solve explicitly. The partition of the plane into cells has cells in the general case, and cells for convex polygons; it can be constructed in an amount of time which is larger than these bounds by a logarithmic factor. Barequet and Rogol claim that in practice the area maximization problem within a single cell can be solved in time, giving (non-rigorous) overall time bounds of for the convex case and for the general case.[7]

Related concepts

de Valcourt (1966) lists 11 different measures of axial symmetry, of which the one described here is number three.[8] He requires each such measure to be invariant under similarity transformations of the given shape, to take the value one for symmetric shapes, and to take a value between zero and one for other shapes. Other symmetry measures with these properties include the ratio of the area of the shape to its smallest enclosing symmetric superset, and the analogous ratios of perimeters.

Lassak (2002), as well as studying axiality, studies a restricted version of axiality in which the goal is to find a halfspace whose intersection with a convex shape has large area lies entirely within the reflection of the shape across the halfspace boundary. He shows that such an intersection can always be found to have area at least 1/8 that of the whole shape.[1]

In the study of computer vision, Marola (1989) proposed to measure the symmetry of a digital image (viewed as a function from points in the plane to grayscale intensity values in the interval ) by finding a reflection that maximizes the area integral[9]

When is the indicator function of a given shape, this is the same as the axiality.

References

  1. 1 2 Lassak, Marek (2002), "Approximation of convex bodies by axially symmetric bodies", Proceedings of the American Mathematical Society, 130 (10): 3075–3084 (electronic), doi:10.1090/S0002-9939-02-06404-3, MR 1908932. Erratum, doi:10.1090/S0002-9939-03-07225-3.
  2. Krakowski, F. (1963), "Bemerkung zu einer Arbeit von W. Nohl", Elemente der Mathematik, 18: 60–61. As cited by de Valcourt (1966).
  3. Choi, Chang-Yul (2006), Finding the largest inscribed axially symmetric polygon for a convex polygon (PDF), Masters thesis, Department of Electrical Engineering and Computer Science, Korea Advanced Institute of Science and Technology.
  4. Nohl, W. (1962), "Die innere axiale Symmetrie zentrischer Eibereiche der euklidischen Ebene", Elemente der Mathematik, 17: 59–63. As cited by de Valcourt (1966).
  5. Buda, Andrzej B.; Mislow, Kurt (1991), "On a measure of axiality for triangular domains", Elemente der Mathematik, 46 (3): 65–73, MR 1113766.
  6. Ahn, Hee-Kap; Brass, Peter; Cheong, Otfried; Na, Hyeon-Suk; Shin, Chan-Su; Vigneron, Antoine (2006), "Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets", Computational Geometry, 33 (3): 152–164, doi:10.1016/j.comgeo.2005.06.001, MR 2188943.
  7. Barequet, Gill; Rogol, Vadim (2007), "Maximizing the area of an axially symmetric polygon inscribed in a simple polygon" (PDF), Computers & Graphics, 31 (1): 127–136, doi:10.1016/j.cag.2006.10.006.
  8. de Valcourt, B. Abel (1966), "Measures of axial symmetry for ovals", Israel Journal of Mathematics, 4: 65–82, doi:10.1007/BF02937452, MR 0203589.
  9. Marola, Giovanni (1989), "On the detection of the axes of symmetry of symmetric and almost symmetric planar images", IEEE Transactions on Pattern Analysis and Machine Intelligence, 11 (1): 104–108, doi:10.1109/34.23119
This article is issued from Wikipedia - version of the 2/7/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.