{"entities":{"Q1102109":{"pageid":1112861,"ns":120,"title":"Item:Q1102109","lastrevid":42878749,"modified":"2025-07-15T15:58:51Z","type":"item","id":"Q1102109","labels":{"en":{"language":"en","value":"A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4049042"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$CF826AE0-C6F1-4F00-AE9E-B70AD084D6EA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3e24fe8bfce44955bc47739018006f4247d22899","datavalue":{"value":{"text":"A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1102109$ADA445C2-1582-4C80-8195-7E8EB3D79E09","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0278e7784d8ad097870d9b6f112017dd4eefc699","datavalue":{"value":"0643.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102109$D31B8335-BCD1-49F1-8ADA-5DEE51A6DAA9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"28b3cc675c0a2a54a7a04e6a5f54df35ba31282d","datavalue":{"value":"10.1007/BF01840368","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102109$93480849-DDE6-4B20-B39E-93F471A868F7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05973d4747711a904c4eb354f325fda834906623","datavalue":{"value":{"entity-type":"item","numeric-id":396765,"id":"Q396765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$966B6DCD-20CC-4685-856B-40D8978F56DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1de24e8908d13cece66a39b7c32dc8ef9790ae08","datavalue":{"value":{"entity-type":"item","numeric-id":1262129,"id":"Q1262129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$5B446A9B-9BD5-4D92-B2DD-DC856B6BBDF0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$2968F750-66F0-4439-81D5-248266B90142","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1102109$70FDB9F9-DD98-4E33-A8BC-1DA996284C72","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0c3242951f58d6345ba6bf833e08affeedf3e277","datavalue":{"value":"We present here a new and efficient algorithm for planning collision-free motion of a line segment (a rod or a ``ladder'') in two-dimensional space amidst polygonal obstacles. The algorithm uses a different approach than those used in previous motion-planning techniques, namely, it calculates the boundary of the (three-dimensional) space of free positions of the ladder, and then uses this boundary for determining the existence of required motions, and plans such motions whenever possible. The algorithm runs in time O(K log n)\\(=O(n^ 2 \\log n)\\) where n is the number of obstacle corners and where K is the total number of pairs of obstacle walls or corners of distance less than or equal to the length of the ladder. The algorithm has thus the same complexity as the best previously known algorithm of \\textit{D. Leven} and the second author [J. Algorithms 8, 192-215 (1987; see the following review)], but if the obstacles are not too cluttered together it will run much more efficiently. The algorithm also serves as an initial demonstration of the viability of the technique it uses, which we expect to be useful in obtaining efficient motion- planning algorithms for other more complex robot systems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102109$A38E3C27-5374-45AE-9CE3-52706877C541","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102109$7E308E80-D0AB-4788-ABC8-F7AB03A6824B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"719fd2949b80c8cc7a58cbc4ca1d7d0d3b69123f","datavalue":{"value":"52-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102109$A33593D1-D9A9-44E6-A688-DDBF5328FD19","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6d3787cecf527e5a1d7caceabc2202626d9a7405","datavalue":{"value":"4049042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102109$A1BD5596-1466-49E9-9AEC-F8AF2F9B8AB6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"baa401a90f7be40837e492046fd0146ae8e354d2","datavalue":{"value":"robotics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102109$111FCE60-02E1-44BC-9B21-4A704036ACBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102109$50E1E41A-BFB3-4C98-AA1A-EFC6B3A95492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbda80faf7c66fe809412afa8394210863f0c0a9","datavalue":{"value":"configuration space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102109$F99122C6-A39C-4A90-9397-E2779C550A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7bb68a0e6d6481788d90b9c9b6b232ad71a66a6","datavalue":{"value":"ladder","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102109$D20F1E0D-A6FA-48EE-BC67-F8C6ED3B85B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8f919bd8e06bf293156a08c7f8364622ce910ea","datavalue":{"value":"polygonal obstacles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102109$3AD7F039-813C-4A3C-849A-4AF93D4CE52C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1a0d8556956f328dc85d4908eb7668485fe869f","datavalue":{"value":"motion-planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102109$27A5D24C-8900-49EA-9CF8-F5D695A8686C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$4DFD2A2E-A69E-4967-84C4-459FCCA0B705","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"90c10f3313dde19a9252305df9d45bc029891d9e","datavalue":{"value":{"entity-type":"item","numeric-id":3049855,"id":"Q3049855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$0C0CED53-165F-4C88-8B68-A583C09E2A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae29f327c59780dea378339b809ffb2bf6e4bd12","datavalue":{"value":{"entity-type":"item","numeric-id":1076976,"id":"Q1076976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$A1620906-C767-4FB6-A25F-74FD894C8B86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4b7b63704e574f5b12162cf3b779d2b3487b8df","datavalue":{"value":{"entity-type":"item","numeric-id":1084674,"id":"Q1084674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$59682B9F-8345-4497-A08F-8CEFF3DC3FBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32a7de3806dff935793f999271e8c8c446568af9","datavalue":{"value":{"entity-type":"item","numeric-id":4119824,"id":"Q4119824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$1BF8BD8B-F891-45D7-AFC0-2699022E6DF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c31401b27b59ab93330106eaaae9b471a83d429","datavalue":{"value":{"entity-type":"item","numeric-id":3736451,"id":"Q3736451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$F0F947F2-7F4C-4ABB-BEAD-46379639E3C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d00fee834e0792b465974b4a515e53fab6ed19d9","datavalue":{"value":{"entity-type":"item","numeric-id":3219802,"id":"Q3219802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$894002CE-275E-45BD-BEAE-077EF85A559E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dca04568c4dfb5342a35fa8c21257c511b7967fb","datavalue":{"value":{"entity-type":"item","numeric-id":1094871,"id":"Q1094871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$F694DB84-DEFF-4AFE-BAF6-B53AE9E328FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f3a00c41c8365dadba43270184930d03ceda008","datavalue":{"value":{"entity-type":"item","numeric-id":3217189,"id":"Q3217189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$F072B9C3-FAD7-4682-9201-D4A33DE41459","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8332468c56cf425ddf859080eb3b69a9207db47c","datavalue":{"value":{"entity-type":"item","numeric-id":760006,"id":"Q760006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$F4FD09A4-B1AD-48C6-BFEE-AD100343F393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43fd89a86be4b43031ef0ae2f7cbc3fbf5a9520d","datavalue":{"value":{"entity-type":"item","numeric-id":3721314,"id":"Q3721314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$04E7F5C6-0DFF-44E7-ADF0-C018BC6C6BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ab148c24a00612e089d62da7acf29e35d25d11e","datavalue":{"value":{"entity-type":"item","numeric-id":3217190,"id":"Q3217190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$F955148B-FA29-46D8-8FD4-6894B0F44CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1d88ae938d00c329356bbc95928aebd825c4600","datavalue":{"value":{"entity-type":"item","numeric-id":3721316,"id":"Q3721316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102109$03CB16A1-2E78-4E63-88C9-3EC47C163D05","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b33ff2037d67d6657b0239baf5788fe4b540836b","datavalue":{"value":"https://doi.org/10.1007/bf01840368","type":"string"},"datatype":"url"},"type":"statement","id":"Q1102109$49F528ED-06B0-43F5-B592-41EC1CFE3A2D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"922c19e2ee8de47bdc3cc6f02594266bcefd9475","datavalue":{"value":"W2061311037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102109$8D637FCF-CA9B-405B-90CE-6AC3096583FF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7be3c7e453e789411a12ae8550270026cb416d04","datavalue":{"value":{"entity-type":"item","numeric-id":1263972,"id":"Q1263972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18e5d79cde0b642747f0a987cc179cf0f024f597","datavalue":{"value":{"amount":"+0.9097911","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102109$38C0819F-3AB2-4730-AF7A-7D58DA15504E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ceb9e7c5cb870898f03cccbb218fafe580d7c32b","datavalue":{"value":{"entity-type":"item","numeric-id":3423757,"id":"Q3423757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c30ab5334805dddb443bb9d93d081365dd8e10f","datavalue":{"value":{"amount":"+0.8743888","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102109$8FD684BD-765A-4C9C-9A84-5CE79D81CAA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3595cec2d6c5c0ef8b9193681c6a50e10ede75d9","datavalue":{"value":{"entity-type":"item","numeric-id":4543584,"id":"Q4543584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ab14ab766946711008eff4ef55257f05c751fd7","datavalue":{"value":{"amount":"+0.87102455","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102109$3A83729A-98A3-4ABF-A470-83576F33E7BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fba8f87336e35434b6ed36be05bb5366ee42b6c","datavalue":{"value":{"entity-type":"item","numeric-id":1923770,"id":"Q1923770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ca9a2bde346d94e357fa9d1c0aa17f1adf8ea99","datavalue":{"value":{"amount":"+0.8660282","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102109$6B30A617-9A8B-48E9-936F-458108C085E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec1a4c9d933fe9a1b5f275359990f69e50fd9bb2","datavalue":{"value":{"entity-type":"item","numeric-id":1307604,"id":"Q1307604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71cdd3865f1d5d4e831dfbba3b8f58fd7ef3f48a","datavalue":{"value":{"amount":"+0.8524811","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102109$3AE2750D-A008-41D6-9CCD-C6B009901B41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13797a0efa711b2f7380b2e4cbc9699723d4cbdf","datavalue":{"value":{"entity-type":"item","numeric-id":3197363,"id":"Q3197363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"121cb06fc7819cd3602d1bddf375eed0c69f9dbc","datavalue":{"value":{"amount":"+0.851993","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102109$AF055FE7-3F6B-4661-9528-2E3B752ABC84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e43bff91379f04d2ad69ed7ad6bbb4ab217475f","datavalue":{"value":{"entity-type":"item","numeric-id":519480,"id":"Q519480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6ef52ffc5129d301d48c32b793b28c105520b21","datavalue":{"value":{"amount":"+0.8498791","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102109$5A59A02F-2AAE-4745-B84E-6EEFB97DBD4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e2656441c332ad56f9471367ebd5c30fefd8f29","datavalue":{"value":{"entity-type":"item","numeric-id":3990095,"id":"Q3990095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcf839eae9e8d709872ab240172a98a9a051927d","datavalue":{"value":{"amount":"+0.84674585","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102109$FD23B778-7E51-4EE1-A781-FBCF0C6CA8BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c5d26029a2d97146b42bf23c26eaf2d71fb9fd7","datavalue":{"value":{"entity-type":"item","numeric-id":1084674,"id":"Q1084674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf9daba78d3a04af9d4ec25391926ae53adbdcbf","datavalue":{"value":{"amount":"+0.8461812","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102109$E618EB7E-2B9B-4668-AF75-AB836CD215CE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1102109","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1102109"}}}}}