On representing a simple polygon perceivable to a blind person

Given the contour of a simple polygon P as an ordered set V of n vertices including a start vertex v, we model the optimization problem of representing P with a smallest-size unordered set S={V∪V′} of vertices, where V′ denotes an additional set of pseudo-vertices chosen along the edges of P such that P is perceivable uniquely by applying a progressive nearest-neighbor traversal rule. A traversal that uses the nearest-neighbor rule on the set S is said to perceive the polygon P if the traversal on S from the same start vertex v∈S visits the vertices in P in the same order when the following rule is applied: Recursively choose the next nearest neighbor v′∈S of v and then delete the last visited vertex v until all the vertices in S is traversed. The set S of vertices by itself should be tangible by touch (tactile information) in the sense that it is able to convey the perception of the shape to a blind reader in the same way as it was described in its input. A desirable objective in this context is to find the smallest-cardinality set V′ such that P can be perceived uniquely from S={V∪V′} using the nearest-neighbor traversal rule. In this paper, we propose to choose a set V⁎ with a sufficiently large cardinality such that the unordered set S⁎={V∪V⁎} can be used to perceive P using the nearest-neighbor traversal rule. We also compute an upper bound on |V⁎| constructed by the proposed algorithm, in terms of certain geometric parameters of the polygon P.