Two-finger caging of concave polygon

Abstract

An object is captured by a set of fingers when there exists no trajectory to bring the object arbitrarily far from the fingers. Object concavity is a special geometric property that allows objects to be captured with only few fingers. In particular, certain concave objects may be captured by appropriately placing two fingers close to some pair of opposite concave sections. This paper addresses the problem of computing all configurations of the fingers that are farthest away from each other while still capable of capturing the object. We propose an O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> lg n) algorithm for this task and present preliminary results showing efficiency of the algorithm