Line Symmetry of Convex Digital Regions

摘要

The line symmetry problem discussed in this paper is formulated as follows: given a setSof digital points, determine ifShas a convex preimageEsuch thatEhas a line of symmetry. HereEdenotes an ordinary convex region from Euclidean plane geometry. We present two algorithms which solve this problem and return an axis of symmetry whenever a symmetric preimage exists. The first has time complexityO(N3log3N) and space complexityO(N3logN), whereNis an upper bound for the coordinates of points inS. The second algorithm has time complexityO(N4log2N) and the space complexityO(NlogN). The stated time and space complexities take into account the precision requirements of the algorithms.