{"entities":{"Q1314439":{"pageid":1325189,"ns":120,"title":"Item:Q1314439","lastrevid":68438760,"modified":"2026-04-12T23:43:04Z","type":"item","id":"Q1314439","labels":{"en":{"language":"en","value":"On the complexity of a single cell in certain arrangements of surfaces related to motion planning"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 502905"}},"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":"Q1314439$B72E15F2-A603-4B25-9BD6-DEB21E5C52F4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"548877d99e3380fd045ebd091cc73221f033a221","datavalue":{"value":{"text":"On the complexity of a single cell in certain arrangements of surfaces related to motion planning","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1314439$F007B551-C96E-4996-978C-1DFC792878B5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"634925af38f23336e936475243b35abdb9d23b2b","datavalue":{"value":"0791.68162","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314439$DE6FE7CE-F795-4A5F-8BF1-DDE03A0E8FD8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c7ace07a10a10bcaf88d49f9b85ee38a59f96a57","datavalue":{"value":"10.1007/BF02573992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314439$91CD5931-199B-4913-85A2-4151BF2FE251","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$F7B4B052-3396-40DF-9F5A-C3DEFEA82A5D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"64aeb88bbb7c1bb9656aaa1ce58528da881ca063","datavalue":{"value":{"time":"+1994-07-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1314439$B35B420B-8391-4133-8F39-11F9ACEAB377","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"92aad0153cca1e0b744c7b5b2a148d0ed7795781","datavalue":{"value":"https://eudml.org/doc/131286","type":"string"},"datatype":"url"},"type":"statement","id":"Q1314439$4105CA37-34E5-48D0-945D-81D12ED49DBE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9eb83371e2c1fc5223df08c092b6431a9e0a015b","datavalue":{"value":"This interesting paper contains results for motion-planning problems with three degrees of freedom where the entire free configuration space could be in cubic size. The author obtains almost tight near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in arrangements of \\(n\\) surfaces in 3-space which are interesting for motion planning problems. He gives also topological and combinatorial conditions for such near-quadratic upper bounds. He studies applications for three- link arm arrangements and for special arrangements of triangles in space.   Among others the following theorem about algorithms is proved: A single cell in an arrangement of surfaces induced by the motion planning for a telescope arm among \\(n\\) point obstacles in the plane can be computed in \\(O(n^ 2\\log^ 2n)\\) time and \\(O(n^ 2\\log n)\\) space.   Interesting open problems are discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314439$90ADE4F4-7A99-4F77-88E7-12AFF92AABBE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314439$5DB3A5A4-391A-425C-8B5D-596D403A3155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7501cba48320d715aa2f92c8f7803347a8901b66","datavalue":{"value":"52C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314439$96580B25-F995-4339-9213-7211E204DA64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314439$4EF543DD-480E-423B-B0C2-567804753109","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e270ca7bde0b9ea0aad8b388f972a8861950c90d","datavalue":{"value":"502905","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314439$4E591EF8-7154-44AB-8901-A16135E661B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b0f1f4e28486b93fe1414ef2f8d97b410c8ee4","datavalue":{"value":"motion-planning problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314439$58385C6E-F6A1-4D5F-9961-89AD4DE5EF5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7a39a1c143c36b9a508b6e0aad9580fb160eda5","datavalue":{"value":"combinatorial complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314439$10073B42-E2D7-4F29-878B-2A8BBE49C770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4d4d9863fad73d4c5b18d81af8cd0585cb60dc4","datavalue":{"value":"arrangements","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314439$FA08E84B-1039-4304-86D4-83D33E02F8C9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"23a41a6deabd7061042ee0e831f408aaabaf33af","datavalue":{"value":{"entity-type":"item","numeric-id":238435,"id":"Q238435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$05F64191-37CA-4057-AFAE-A2AE73975DA9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f97401dc38cdab90e116741461a88db9a2626407","datavalue":{"value":{"entity-type":"item","numeric-id":701798,"id":"Q701798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$A79E8B91-DB9E-47EA-B84E-72AE102C0A93","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":"Q1314439$215B8D5A-5E56-472E-B328-124F83C8BEDE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf7badab20497520986499f0322c7ee69861295d","datavalue":{"value":{"entity-type":"item","numeric-id":1189286,"id":"Q1189286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$5A706025-0267-4481-8A70-6C86BE5AF3FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"697aae026a155134884ccf2d1f0ab3c5ec550b9e","datavalue":{"value":{"entity-type":"item","numeric-id":2638823,"id":"Q2638823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$5F4DC385-42DB-4D9D-B660-DCCA26840A05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e9e1629289c17adbbe0b8b3786cfc15c2541b48","datavalue":{"value":{"entity-type":"item","numeric-id":4725255,"id":"Q4725255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$87139B70-53D1-4BAC-9FB6-093E24B7692C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59c2ca0e844db29ecd39f75f5228862dbc02c307","datavalue":{"value":{"entity-type":"item","numeric-id":3138981,"id":"Q3138981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$88990104-4576-4970-8BD5-CAD711544A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e264934c2583d53de4ec56667117a09231208f7","datavalue":{"value":{"entity-type":"item","numeric-id":3795219,"id":"Q3795219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$056915B6-4344-49CB-8EDC-26D093EA87F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba1eef9a8de19b57864dc87d5c058554f9d6c7cf","datavalue":{"value":{"entity-type":"item","numeric-id":582900,"id":"Q582900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$E58E25DD-3C5C-4624-A495-3BB34782B2E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd9e4c821f40dcda02ef9c4e0bbe7776dc478a23","datavalue":{"value":{"entity-type":"item","numeric-id":3138742,"id":"Q3138742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$0057B812-EBCD-4C6B-8307-72D1ABE8DACE","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":"Q1314439$2893A301-6B1F-4A5A-AA0E-E521B45C635D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9242e138bb11891456ae39a32ac5319c3f8bf378","datavalue":{"value":{"entity-type":"item","numeric-id":3990095,"id":"Q3990095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$F54A51E2-6318-440F-96E4-D8CDF9C43CB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2c5168d419e753032c3f2639c8b58971bb8571c","datavalue":{"value":{"entity-type":"item","numeric-id":1194309,"id":"Q1194309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$7BF936BF-E859-477D-A9A6-764CADE1D467","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":"Q1314439$396D015E-3FAD-4E57-A271-406A974731F2","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":"Q1314439$89C1B810-E0BE-46CA-8EB4-937DAB37A76A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20c194bcbdefa928c498e04e227e2d6f4aa5733c","datavalue":{"value":{"entity-type":"item","numeric-id":3785936,"id":"Q3785936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$F9D7F393-21E0-4145-B1F5-E2C41AA002D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7268624479a5bc435fdb2e9183ce011e018dd2bd","datavalue":{"value":{"entity-type":"item","numeric-id":810525,"id":"Q810525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$AF3B1F67-390D-42A8-B2C1-A82203903AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"584205de1d391987ee461758c5d4a00a1c3eaf66","datavalue":{"value":{"entity-type":"item","numeric-id":1104080,"id":"Q1104080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$1FC291DB-8620-4F45-AB39-BD2D2899C731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce778d21d638bc1f0cfa72f75db8e16ba2191a90","datavalue":{"value":{"entity-type":"item","numeric-id":1102109,"id":"Q1102109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$E6B0C925-1F4B-43BE-BF53-9B0788A54F1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dd1104c3819dc61bbacb583d9a9ffa28e54bb09","datavalue":{"value":{"entity-type":"item","numeric-id":1098294,"id":"Q1098294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314439$08E116B8-4257-4F58-91B5-79113B39308F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8ffaaf040608920e46ab639fe2c95697fe67da2b","datavalue":{"value":"W2122272881","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314439$3ED27D33-4125-4670-9244-DB6A942B29EA","rank":"normal"}],"P1643":[{"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":"3ec19509f4c2dd726502549285e10f5a05a600f0","datavalue":{"value":{"amount":"+0.885948896408081","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":"Q1314439$57FDE8F5-4A9B-4601-9C9D-6DF1423B1F26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"897f53f50f58bf0fbb26db02110020047cd06481","datavalue":{"value":{"entity-type":"item","numeric-id":1842755,"id":"Q1842755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d271bcc062b00f0549dbd8817aa90c60f6646ffa","datavalue":{"value":{"amount":"+0.8440033197402954","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":"Q1314439$99B4031C-CCE1-42C4-AFFF-E8198A846D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3d6d3dd2e756480d60787ef0a907babd9d51ffc","datavalue":{"value":{"entity-type":"item","numeric-id":1906044,"id":"Q1906044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf3bf644641ef12922a68f0e4bf4e0af5d999096","datavalue":{"value":{"amount":"+0.8386209011077881","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":"Q1314439$FDE95F6D-E21F-46BC-99FB-6C3A0C00A635","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of a single cell in certain arrangements of surfaces related to motion planning","badges":[]}}}}}