Attraction-convexity and normal visibility

摘要

Beacon attraction, or simply attraction, is a movement system whereby a point moves in a free space so as to always locally minimize its Euclidean distance to an activated beacon (also a point). This results in the point moving directly towards the beacon when it can, and otherwise sliding along the edge of an obstacle or being stuck (unable to move). When the point can reach the activated beacon by this method, we say that the beacon attracts the point. In this paper, we study attraction-convex polygons, which are those where every point in the polygon attracts every other point. We find that these polygons are a subclass of weakly externally visible polygons, which are those where every point on the boundary is visible from some point arbitrarily distant (or at infinity on the projective plane). We propose a new class of polygons called normally visible, and show that this is exactly the class of attraction-convex polygons. This alternative characterization of attraction-convex polygons leads to a simple linear-time attraction-convex polygon recognition algorithm. We also give a Helly-type characterization of inverse-attraction star-shaped polygons. (C) 2021 Elsevier B.V. All rights reserved.