TY - JOUR

T1 - Computing all immobilizing grasps of a simple polygon with few contacts

AU - Cheong, J.-S.

AU - Haverkort, H.J.

AU - van der Stappen, A.F.

PY - 2006

Y1 - 2006

N2 - We study the output-sensitive computation of all the combinations of edges and concave vertices of a simple polygon that allow an immobilizing grasp with less than four frictionless point contacts. More specifically, if n is the number of edges, and m is the number of concave vertices of the polygon, we show how to compute: in O(m4/3 log1/3 m + K) time, all K combinations that allow a form-closure grasp with two contacts; in O(n2 log4 m + K) time, all K combinations that allow a form-closure grasp with three contacts; in O(n log4 m + (nm)2/3 log2+e m + K) time (for any constant e > 0), all K combinations of one concave vertex and one edge that allow a grasp with one contact on the vertex and one contact on the interior of the edge, satisfying Czyzowicz's weaker conditions for immobilization; in O(n2 log3 n + K) time, all K combinations of three edges that allow a grasp with one contact on the interior of each edge, satisfying Czyzowicz's weaker conditions for immobilization.

AB - We study the output-sensitive computation of all the combinations of edges and concave vertices of a simple polygon that allow an immobilizing grasp with less than four frictionless point contacts. More specifically, if n is the number of edges, and m is the number of concave vertices of the polygon, we show how to compute: in O(m4/3 log1/3 m + K) time, all K combinations that allow a form-closure grasp with two contacts; in O(n2 log4 m + K) time, all K combinations that allow a form-closure grasp with three contacts; in O(n log4 m + (nm)2/3 log2+e m + K) time (for any constant e > 0), all K combinations of one concave vertex and one edge that allow a grasp with one contact on the vertex and one contact on the interior of the edge, satisfying Czyzowicz's weaker conditions for immobilization; in O(n2 log3 n + K) time, all K combinations of three edges that allow a grasp with one contact on the interior of each edge, satisfying Czyzowicz's weaker conditions for immobilization.

U2 - 10.1007/s00453-005-1202-x

DO - 10.1007/s00453-005-1202-x

M3 - Article

VL - 44

SP - 117

EP - 136

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 2

ER -