{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:48:28Z","timestamp":1777715308222,"version":"3.51.4"},"reference-count":45,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[1994,2,1]],"date-time":"1994-02-01T00:00:00Z","timestamp":760060800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[1994,2]]},"abstract":"<jats:p>Our objective is to automatically recognize parts in a struc tured environment (such as a factory) using inexpensive and widely available hardware. In this article we consider the pla nar problem of determining the convex shape of a polygonal part from a sequence of projections. Projecting the part onto an axis in the plane of the part produces a scalar measure, the diameter, which is a function of the angle of projection. The diameter of a part at a particular angle can be measured using an instrumented parallel-jaw gripper.<\/jats:p>\n                  <jats:p>First, we present the negative result that shape cannot be uniquely recovered: for a given set of diameter measurements, there is an (uncountably) infinite set of polygonal shapes con sistent with these measurements. Because most of these shapes have parallel edges of varying lengths, we consider the related problem of identifying a representative polygon with no par allel edges. We show that, given a diameter function, deciding whether such a polygon exists is NP-complete.<\/jats:p>\n                  <jats:p>\n                    These results motivate us to consider the problem of recog nizing a part from a known (finite) set of parts. Given a set of polygonal parts with a total of N faces, can we find the short est sensing plan for disambiguating the parts? Only diameters at n \u2264 N stable faces can be measured. We construct an in ternal representation of these stable diameters in O(N + n\n                    <jats:sup>3<\/jats:sup>\n                    ) time and then give two planning algorithms: one constructs an optimal sensing plan in time O( n\n                    <jats:sup>4<\/jats:sup>\n                    2\n                    <jats:sup>n<\/jats:sup>\n                    ), the other constructs a suboptimal sensing plan in time O( n\n                    <jats:sup>2<\/jats:sup>\n                    log n). Neither plan requires more than n measurements.\n                  <\/jats:p>","DOI":"10.1177\/027836499401300102","type":"journal-article","created":{"date-parts":[[2007,3,4]],"date-time":"2007-03-04T20:24:06Z","timestamp":1173039846000},"page":"16-37","source":"Crossref","is-referenced-by-count":39,"title":["Shape from Diameter"],"prefix":"10.1177","volume":"13","author":[{"given":"Anil S.","family":"Rao","sequence":"first","affiliation":[{"name":"Department of Computer Science Utrecht University, Padualaan 14 3508 TB Utrecht, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenneth Y.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Institute of Robotics and Intelligent Systems University of Southern California Los Angeles, California 90089-0273"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[1994,2,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/5.5968"},{"key":"atypb2","volume-title":"Euclidian Geometry and Convexity","author":"Benson, R.V.","year":"1966"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293035"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758849"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1177\/027836498800700101"},{"key":"atypb6","volume-title":"A RISC paradigm for industrial robotics. Technical report ESRC 93-4\/RAMP 93-2. Engineering Systems Research Center","author":"Canny, J.","year":"1993"},{"key":"atypb7","volume-title":"Symposium on Discrete Algorithms (SODA). SIAM-ACM","author":"Chandru, V."},{"key":"atypb8","volume-title":"Distinguishing polygons by sensing diameters. Technical report USC-CS-92-503. Dept. of Computer Science","author":"Chen, Y.-B.","year":"1991"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90025-3"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"Dobkin, D.P., Edelsbrunner, H., and Yap, C.K. 1986. Probing convex polytopes. Symposium on Theory of Computing, ACM. pp. 424-432.","DOI":"10.1145\/12130.12174"},{"key":"atypb12","volume-title":"Algorithms in Combinational Geometry. EATCS Monographs on Theoretical Computer Science","author":"Edelsbrunner, H.","year":"1987"},{"key":"atypb13","volume-title":"IEEE International Conference on Robotics and Automation","author":"Ellis, R."},{"key":"atypb14","volume-title":"IEEE International Conference on Robotics and Automation","author":"Erdmann, M.A."},{"key":"atypb15","volume-title":"Computers and Intractibility: A Guide to the Theory of NP-Completeness","author":"Garey, M.","year":"1979"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1984.4767518"},{"key":"atypb17","volume-title":"Stochastic plans for robotic manipulation. Ph.D. thesis. School of Computer Science","author":"Goldberg, K.Y.","year":"1990"},{"key":"atypb18","first-page":"2","volume":"1","author":"Goldberg, K.Y.","year":"1993","journal-title":"Algorithmica"},{"key":"atypb19","volume-title":"Low friction gripper","author":"Goldberg, K.Y.","year":"1992"},{"key":"atypb20","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TPAMI.1987.4767935","volume":"9","author":"Grimson, W.E.L.","year":"1987","journal-title":"IEEE Trans. Pattern Analysis and Machine Intelligence"},{"key":"atypb21","volume-title":"Analytic techniques for automated grasp. Ph.D. thesis","author":"Jameson, J.","year":"1985"},{"key":"atypb22","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Kang, D."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187723"},{"key":"atypb24","volume-title":"Object exploration using a parallel-jaw gripper. GRASP lab tech report MS-CIS-88-48","author":"Koutsou, A.","year":"1988"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90091-3"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90196-2"},{"key":"atypb27","volume-title":"On the scope of quasi-static pushing","author":"Mason, M.T.","year":"1986"},{"key":"atypb28","volume-title":"Planning sequences of squeeze-grasps to orient and grasp polygonal objects. Technical report CMU-CS-88-127. Computer Science Dept","author":"Mason, M.T.","year":"1988"},{"key":"atypb29","volume-title":"Planning Robotic Manipulation Strategies for Sliding Objects. Ph.D. thesis. Department of Physics","author":"Peshkin, M.A.","year":"1986"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"atypb31","volume-title":"Grasping planar curved parts with a parallel-jaw gripper. Technical report no. 299. Institute of Robotics and Intelligent Systems (IRIS)","author":"Rao, A.S.","year":"1992"},{"key":"atypb32","volume-title":"International Conference on Robotics and Automation","author":"Rao, A.S."},{"key":"atypb33","volume-title":"Shape from diameter: Strategies for recognizing polygonal parts. Technical report no. 292. Institute of Robotics and Intelligent Systems (IRIS)","author":"Rao, A.S.","year":"1992"},{"key":"atypb34","volume-title":"Algorithmic Plans for Robotic Manipulation. Ph.D. thesis. Department of Electrical Engineering-Systems","author":"Rao, A.S.","year":"1992"},{"key":"atypb35","volume-title":"Annual Symposium on Computational Geometry, ACM","author":"Rappaport, D."},{"key":"atypb36","volume-title":"International Conference on Computer Vision and Pattern Recognition","author":"Raviv, D."},{"key":"atypb37","volume-title":"Artificial Intelligence","author":"Rich, E.","year":"1983"},{"key":"atypb38","volume-title":"Geometric Probing. Ph.D. thesis. Dept. of Computer Science","author":"Skiena, S.S.","year":"1988"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553911"},{"key":"atypb40","volume-title":"International Conference on Robotics and Automation","author":"Spyridi, A.J."},{"key":"atypb41","volume-title":"Fourth International Symposium on Robotics Research","author":"Taylor, R.H."},{"key":"atypb42","volume-title":"Linear time algorithm for object localization using scanning","author":"Wallack, A.S.","year":"1991"},{"key":"atypb43","volume-title":"Object localization using finger gap sensing. Technical report ESRC 92-3\/RAMP 92-2. Dept. of Computer Science","author":"Wallack, A.S.","year":"1992"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1117\/12.164990"},{"key":"atypb45","volume-title":"Convex Figures","author":"Yaglom, I.M.","year":"1951"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499401300102","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499401300102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:14:47Z","timestamp":1777457687000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836499401300102"}},"subtitle":["Recognizing Polygonal Parts With a Parallel-Jaw Gripper"],"short-title":[],"issued":{"date-parts":[[1994,2]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,2]]}},"alternative-id":["10.1177\/027836499401300102"],"URL":"https:\/\/doi.org\/10.1177\/027836499401300102","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,2]]}}}