Computing all immobilizing grasps of a simple polygon with few contacts

J.-S. Cheong, H.J. Haverkort, A.F. van der Stappen

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)117-136
JournalAlgorithmica
Volume44
Issue number2
DOIs
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Computing all immobilizing grasps of a simple polygon with few contacts'. Together they form a unique fingerprint.

Cite this