{"entities":{"Q1096427":{"pageid":1107179,"ns":120,"title":"Item:Q1096427","lastrevid":66294003,"modified":"2026-04-12T08:53:05Z","type":"item","id":"Q1096427","labels":{"en":{"language":"en","value":"Motion planning among time dependent obstacles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4031062"}},"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":"Q1096427$823FE55B-AEC9-4D53-891A-ECD233042C19","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7e4a6dd042f0e2f4aaf9bcad2c871a0f40246ddf","datavalue":{"value":{"text":"Motion planning among time dependent obstacles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1096427$F369B30C-8008-4737-AEF0-9D5E7E9FFD2E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f5ad1fb8ebd8321ed15fbf5f137928e42ff83ec","datavalue":{"value":"0633.68117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096427$82AF5324-73DA-4F4A-B5C7-D36C2F4DF0AF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"37a45cb44e8cef93af5dfa8016ffd695ba7c7763","datavalue":{"value":"10.1007/BF02915447","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096427$0911ED76-0557-43DD-9487-E91097DA4CA7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096427$CE4C2CFC-5FD4-465A-8744-823DEB258970","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1096427$3852F7FD-3820-46D2-96BF-918FC1E5E9CE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dc6307d63ae125449206ca14d9fba95b35b9324a","datavalue":{"value":"In this paper motion planning in the presence of time dependent, i.e. moving, obstacles is studied. More specifically, consider the following problem: given a body B and a collection of moving obstacles in D- dimensional space, decide whether there is a continuous, collision-free movement of B from a given initial position to a target position subject to the condition that B cannot move any faster than some fixed top-speed c. As a discrete, combinatorial model for the continuous, geometric motion planning problem time-dependent graphs are introduced. It is shown that a path existence problem in time-dependent graphs is PSPACE- complete. Using this result one can show that a version of the motion planning problem (where the obstacles are allowed to move periodically) is PSPACE-hard, even if \\(D=2\\), B is a square and the obstacles have only translational movement. For \\(D=1\\) it is shown that motion planning is NP- hard.    Define the c-hull of an obstacle to be the collection of all positions in space-time at which a future collision with the obstacle cannot be avoided. In the low-dimensional situation \\(D=1\\) and \\(D=2\\) polynomial-time algorithms for the computation of the c-hull as well as for the motion planning problem are given. In particular for \\(D=1\\) there is a O(n log n) time algorithm for the motion planning problem where n is the number of edges of the obstacles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096427$AAA3CDBA-2768-4821-87C1-D2528AB18508","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096427$79853DDA-FBF4-4D5A-8266-050D623743C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096427$AAC866DF-68ED-4549-AD71-1925E0486E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096427$CA20712D-48DB-4EA7-B337-B55A62468125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"85991e41d5921c9f733fe99d088c198a921df086","datavalue":{"value":"68T99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096427$9E26DE88-E284-4831-AC66-718ADB887FA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096427$92E2C41C-0A8B-41C4-8BB8-3485B8296FB9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bbde7d2117536fb195cde581f4ea5adb9544543a","datavalue":{"value":"4031062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096427$5448A19D-41D9-485C-B716-97736015F0C0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3c4174a5d716f293c7527ce1cefdfb920908bc","datavalue":{"value":"motion planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096427$E5962848-9D93-4A70-AA62-6582CFB056EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de95735fe337792d0796a58e3514b143c6694683","datavalue":{"value":"moving obstacles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096427$DA5623B4-2085-4B24-9B9F-63A7A4FE58E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03daf222d828090779a7812016547c07c42f6712","datavalue":{"value":"time-dependent graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096427$6E7138E0-EF33-4B7D-BBC8-F5037026F737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c41434015e83678a44e5885c948e73dc99599567","datavalue":{"value":"path existence problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096427$3A7A17FE-89B8-4FB0-9E0A-B614ADE9D3F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc5347b3ecbe276359ba24fe48e03c241989ac43","datavalue":{"value":"c-hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096427$6972838D-5F37-4459-8BF3-815A636C2B4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a92166f5adeebffc8c81c6abb980ed495030be8","datavalue":{"value":"polynomial-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096427$C5E78F56-19BD-4AD5-B4B2-C5B991E66FFD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"76d23f26f6787161a9ee593a4d52eb07b076ba50","datavalue":{"value":{"entity-type":"item","numeric-id":616505,"id":"Q616505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096427$23B17349-6A11-4178-BD4C-0AA4530F9D1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d78494649a50abfeb7718b8ac650c7c073c553a9","datavalue":{"value":{"entity-type":"item","numeric-id":353853,"id":"Q353853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096427$8C3EA85E-90FB-4217-AF42-362430BAC7DD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8564e78441affe432e0619719bb2eec6830d68d9","datavalue":{"value":{"entity-type":"item","numeric-id":616505,"id":"Q616505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096427$1D5B7D4D-AFB7-4446-913A-713DDC301777","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":"Q1096427$2A5A3D60-3CD9-4836-9DAA-3E0EC37406DB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"97e62804e938878810cbddd988a8c8345ecb627d","datavalue":{"value":{"entity-type":"item","numeric-id":3731032,"id":"Q3731032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096427$595BDE57-E956-483C-88FB-1A999D892AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096427$329DAE2A-7C10-4842-A407-4688A9F04E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26ae0f668877a3249e49ead957b257c29ff0bb3c","datavalue":{"value":{"entity-type":"item","numeric-id":4310844,"id":"Q4310844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096427$C0E6A244-D87B-4964-A1C0-DCF5480D1F80","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":"Q1096427$D8DFA86E-2897-4286-9CA6-65DE0C9468A0","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":"Q1096427$788FF798-8981-40FC-9D32-BEADBA1B0800","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":"Q1096427$FB0F8DB1-49F8-4AFC-87FA-2D5292F0C00B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"189879fb5064b6be174245e770bfe4a02ea627dd","datavalue":{"value":{"entity-type":"item","numeric-id":794168,"id":"Q794168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096427$AED5A44D-8BA8-4AB9-9EAD-510D8EC34F20","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62442cd6f20a0da6aa47cb7d145ad737165e25ca","datavalue":{"value":{"entity-type":"item","numeric-id":4310844,"id":"Q4310844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3137771eb31481a2f970b703324d8fed96b1e2e6","datavalue":{"value":{"amount":"+0.8652867078781128","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096427$3304670A-902D-4949-BA42-0812D4538E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f96d84ac8a8b0bcebd18b73e3f43badc18cb456","datavalue":{"value":{"entity-type":"item","numeric-id":3728030,"id":"Q3728030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3137771eb31481a2f970b703324d8fed96b1e2e6","datavalue":{"value":{"amount":"+0.8652867078781128","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096427$53707029-739F-4D9A-A3A0-6B05B6C619DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c39311d137727f5f948c50bfb0465abfbb3f8ea2","datavalue":{"value":{"entity-type":"item","numeric-id":5958315,"id":"Q5958315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afc883398ca56a1c16a8891051bb979d09818f06","datavalue":{"value":{"amount":"+0.8108776807785034","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096427$CB0AAF8F-0B78-419E-9046-66C1BFE7AF10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66ca111dd9f375a0240e47e238d6b088aa7bec6e","datavalue":{"value":{"entity-type":"item","numeric-id":1261288,"id":"Q1261288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e31cb636d09e53dceeeabb1804e299dcc1964e7","datavalue":{"value":{"amount":"+0.8063808679580688","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096427$57753BF4-7852-471E-81D4-C4706DC34A8B","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":"a0033fa7a995c48a1ae622a4785cd56e320ec594","datavalue":{"value":{"amount":"+0.8008912205696106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096427$51A86E01-6822-4F37-A8CA-7433D2B95F0D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Motion planning among time dependent obstacles","badges":[]}}}}}