{"entities":{"Q1201745":{"pageid":1212494,"ns":120,"title":"Item:Q1201745","lastrevid":70266105,"modified":"2026-04-13T13:36:24Z","type":"item","id":"Q1201745","labels":{"en":{"language":"en","value":"Approximate motion planning and the complexity of the boundary of the union of simple geometric figures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 98403"}},"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":"Q1201745$1D8CE0F8-A902-4E75-B4AB-ACA873A4E608","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"10d2db52da0ad7d8f01575e16a000c962a0c25c6","datavalue":{"value":{"text":"Approximate motion planning and the complexity of the boundary of the union of simple geometric figures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1201745$2E9B2C62-DB3F-44A3-A7C0-C973D2E8E8C0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f087c5b5c26f6c25a79007d6b27d4001ad61bbf1","datavalue":{"value":"0760.68082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201745$8B4D7771-809F-477F-BDC4-B9D6F519942E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"317b5f8ecb2ebe524fc0e85bcd6429f1133e56f6","datavalue":{"value":"10.1007/BF01758853","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201745$F4EA14E0-7DFF-4D7A-B547-9D102E76B9A5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf6d8016a36fc077e217d8fd7040d00a29999d1c","datavalue":{"value":{"entity-type":"item","numeric-id":671402,"id":"Q671402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$0ABE395A-A674-4E26-8231-A08CCC8C82D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e947c4fb3921699925780ed35d41c9af62d536b","datavalue":{"value":{"entity-type":"item","numeric-id":344818,"id":"Q344818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$80E15B8D-062A-4472-A048-4A8DA0FE9D03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93f2bc7106f436b3e95136cb7027e49039db559e","datavalue":{"value":{"entity-type":"item","numeric-id":270030,"id":"Q270030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$7CD0F0DC-FEE7-404E-8E22-EE71EBA98745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95131789f3ce9737ff874e70984afb7d18bd2ea3","datavalue":{"value":{"entity-type":"item","numeric-id":908707,"id":"Q908707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$09FC8952-5007-407C-B0BA-AE8FAF357978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05eea7654cb0d0157b7f1411c545a76a3d53873a","datavalue":{"value":{"entity-type":"item","numeric-id":655161,"id":"Q655161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$1DA23B54-1547-4DDD-9977-1CD5D953EA6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f012196ada22b97d9d00d44b6a51141308e0402","datavalue":{"value":{"entity-type":"item","numeric-id":441885,"id":"Q441885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$D119D0ED-1F3F-4AAE-81A1-159C2A887309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4e9ef762c8d1726162c87050d097afa76c35dfe9","datavalue":{"value":{"entity-type":"item","numeric-id":1286478,"id":"Q1286478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$353D6A79-603D-4F73-8E9D-3D7ED89C831F","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":"Q1201745$936DEE00-3832-493D-A029-F9314C83F368","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0879f591850b4f9f14b2c481d3e08995aa22089","datavalue":{"value":{"time":"+1993-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1201745$EA0F9A81-2191-4957-819A-F94977E43FDB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"286c55766fed8a29df0cef3b4cecb07c6995156e","datavalue":{"value":"It is proposed to estimate time complexity of motion planning algorithms in terms of both the problem size and the tightness parameter; the latter is intuitively the amount of scaling of the movable object which turns the problem from solvable to unsolvable or conversely.   An algorithm for motion planning of the rectangle in the plane amidst polygonal obstacles with the complexity \\(O(((a/b)(1/t)+1)n\\log^ 2 n)\\) is proposed, where \\(t\\) is for tightness. For ``non-tight'' problems, this significantly improves the known \\(\\Omega(n^ 2)\\) upper bounds. As a technical contribution, the complexities of boundaries of unions of some simple figures are presented. This leads to \\(O((1/a)n\\log^ 2 n)\\) motion planning for a rectangle which may be rotated by angles less than \\(a\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201745$DF3D8D41-66FB-4257-9365-C5CE3B9C4524","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"257d0165052e5019ac8fd49a93c7aebbdcc243c0","datavalue":{"value":{"entity-type":"item","numeric-id":751866,"id":"Q751866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$9F34377F-38D0-4E39-8E3F-A9BD1DBEF8FE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201745$B193CCA2-58BA-4C36-B476-9E2D0617CA8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201745$C973D9FD-19E4-4D97-849C-9F8817BAB2F4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e4b34fb597f9854dd502bcffcf2b71b80cb354e","datavalue":{"value":"98403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201745$0716B2DB-BEBD-4CF1-9882-37CE3BB2FCF9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3c4174a5d716f293c7527ce1cefdfb920908bc","datavalue":{"value":"motion planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201745$AF241C9B-4B22-444D-8E94-0C2F63530B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c856e9cd044be28d88c5f7fa8d75f57259c8412","datavalue":{"value":"rectangle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201745$04E17806-3093-4023-A4B5-B40E507C6889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc6df83a4e8c59752beb0b9effd0645a120e57bb","datavalue":{"value":"obstacles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201745$8BA190C9-D7F3-4A8E-AD43-395E438F7017","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":"Q1201745$C6DA0BDC-D40E-481A-AED6-D59A96253935","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e29b8e47936578f5cad24b50941e85f6a32ad9da","datavalue":{"value":{"entity-type":"item","numeric-id":3738618,"id":"Q3738618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$26AE2FD9-9C3C-43B1-BC64-763190072998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f7e43b624a4c37c3d64eb59c9ae4ec05b06aa27","datavalue":{"value":{"entity-type":"item","numeric-id":1262130,"id":"Q1262130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$3D400428-F2C3-4A49-BFF1-8B710E77A162","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":"Q1201745$15251683-4537-4C9C-AFF6-6BDDB2C625B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d521e82b98b3b40354447c326db589a14024135e","datavalue":{"value":{"entity-type":"item","numeric-id":1263972,"id":"Q1263972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201745$7C7548B8-BAE9-4095-869A-BC1A1739BF0C","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":"Q1201745$DC7772B3-F0D4-4EB3-98BE-BE472CCE3232","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0488a011d3aad4dc6ce8f7a313633a624a1bc655","datavalue":{"value":"https://doi.org/10.1007/bf01758853","type":"string"},"datatype":"url"},"type":"statement","id":"Q1201745$07091910-497E-4E14-9F25-1029F4CA539A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c5552a31bef150dec1c9ec1fa5b2aa173475cd2c","datavalue":{"value":"W2027190503","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201745$F99AF53B-4BBA-4AE5-ABCC-7B5F887583D2","rank":"normal"}],"P1643":[{"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":"9af6bf2de48286e1ef97fb9ffec5b41f23540c32","datavalue":{"value":{"amount":"+0.8081315755844116","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":"Q1201745$EAD4A9D5-731A-4F8D-8E40-0080C7843A5D","rank":"normal"},{"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":"eb3e98772393ec9af7c7138e45367a07d91a77fe","datavalue":{"value":{"amount":"+0.8067307472229004","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":"Q1201745$A3AA1878-B4BC-4587-B58E-936519AD6FB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4b290777081c257774db8aa421825f427b05e75","datavalue":{"value":{"entity-type":"item","numeric-id":3716332,"id":"Q3716332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e6e60df9bb619ac96b1cdac983c4819e0b9d9af","datavalue":{"value":{"amount":"+0.7959187626838684","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":"Q1201745$17518AB7-02C6-4DFE-BB7D-97BBAFC7718D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b291911a1ca25d8c50f3f0d6354f7b10df9908c","datavalue":{"value":{"entity-type":"item","numeric-id":1194309,"id":"Q1194309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb2e5efb6f377427549938617554a5629e057395","datavalue":{"value":{"amount":"+0.786403477191925","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":"Q1201745$933E96EB-9D71-48F5-B44D-BF5ADC3B6AED","rank":"normal"},{"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":"6916f2966a19d37afe1baef9957131db99620b16","datavalue":{"value":{"amount":"+0.7861770987510681","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":"Q1201745$23DBC707-B3A2-483B-BCF1-13E80247A441","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximate motion planning and the complexity of the boundary of the union of simple geometric figures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximate_motion_planning_and_the_complexity_of_the_boundary_of_the_union_of_simple_geometric_figures"}}}}}