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 can be captured by appropriately placing two fingers close to some pair of opposite concave sections. This work addresses the problem of computing all configurations of the two fingers that capable of capturing the object. Those configurations will be represented in such a way that answering whether a finger configuration can capture the object requires O(lgn) running time in most cases (where n is the number of vertices of the object.) In computing all configurations capable of capturing the object, we proposed a O(n[superscript2]lgn) algorithm