{"entities":{"Q1111039":{"pageid":1121788,"ns":120,"title":"Item:Q1111039","lastrevid":49219291,"modified":"2026-01-06T19:11:41Z","type":"item","id":"Q1111039","labels":{"en":{"language":"en","value":"A tight lower bound for the complexity of path-planning for a disc"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4074553"}},"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":"Q1111039$2E12CDF4-7640-47EB-8151-BEAE3453A1A7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cba084f48e4ed1f39e1b4c1da35a8f1adaa577d5","datavalue":{"value":{"text":"A tight lower bound for the complexity of path-planning for a disc","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111039$132EE407-BBC9-4412-A127-DEA19A254A3E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d52926d006abc3a2a5ed8bb0e946363d06b23423","datavalue":{"value":"0657.68115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111039$FC256CD4-4811-4B16-874A-773979C1D4AE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"26d58805c0015ed1f69958f0bfd2fe5bdb27e4bd","datavalue":{"value":"10.1016/0020-0190(88)90203-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111039$9B449F31-D12C-4773-8650-D8E519E331D5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111039$A55ECF99-46FA-440D-AC2D-CADE77366340","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":"Q1111039$68A18302-7B68-426A-8EB0-228E79625643","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"52c376f52c069940ab394d981578d272a6a00842","datavalue":{"value":"Given two points in a planar room with polygonal boundary and polygonal obstacles (having a total of n corners), the problem of finding a shortest obstacle-avoiding path between them is known to require \\(\\Omega\\) (n log n) time. In this article it is shown that the problem of finding any obstacle-avoiding path for a disc in the room, or even deciding whether such a path exists, requires \\(\\Omega\\) (n log n) time. This bound is met by the published algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111039$CEDBEC86-41CA-4A0B-9C0E-15E600E8AA14","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111039$406ACB8D-C92C-4855-80AA-37EA7DA5455D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111039$95E8FEA5-D0B7-4820-A366-7A97B64CF701","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1ed7add0ab0cdc33938998403d49de94efa88c22","datavalue":{"value":"4074553","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111039$8A11A385-6F03-4EF5-93BF-D92EAE44F0DA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3c4174a5d716f293c7527ce1cefdfb920908bc","datavalue":{"value":"motion planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111039$85F2BF93-2257-43CE-A94A-A4E1E0999212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111039$FBFAD92F-4EBA-4F9B-84BB-9121D73FDF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f49eac3d475d0f4a86abc65b8f18d4edc7cac7dc","datavalue":{"value":"algebraic decision tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111039$6DD43DF4-BE11-409C-90E9-D9E6629AE9D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aed274e58471806e973e3926af8e50abb8242477","datavalue":{"value":{"entity-type":"item","numeric-id":1162143,"id":"Q1162143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111039$FC2DD69C-50E9-4018-860E-2415EFB22701","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":"Q1111039$4CAB980E-5E49-446F-A5EC-AE2DE7CC3DDE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c267346430067c71aba498d6a8d7a4c7d3c1c1d0","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90203-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111039$09DFD5E8-8C71-4627-8516-47A8BC37A39C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e9fd97923ed00e9450a46fdf5b1d957a5601633c","datavalue":{"value":"W2077643376","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111039$C3B46C0A-9489-4221-B6C0-9EBDA0DC306A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1690541b69e9e74e7dfc11287316ec76c94d3cb","datavalue":{"value":{"entity-type":"item","numeric-id":3716331,"id":"Q3716331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111039$B3676DC2-7362-4072-B04E-4CF89AFE1C07","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":"Q1111039$86979580-DFAB-4EEB-BE85-459BD9BCB63A","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":"Q1111039$310D00FB-DE07-4A3F-BEF5-47520CF91C17","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":"Q1111039$070736AB-1FAE-4F4A-8060-6474DF58296A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ffec4d94b7b012095f39126ed96f3bf822347da","datavalue":{"value":{"entity-type":"item","numeric-id":1062764,"id":"Q1062764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111039$D990D3C7-C616-4C5F-96E6-9AC1395F4422","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f774e8b4a69d635606ed04517ef79ce6592f5c4","datavalue":{"value":{"entity-type":"item","numeric-id":4323731,"id":"Q4323731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"136cbf6efe536fc4ff5f858000d4224363fb96a0","datavalue":{"value":{"amount":"+0.7950337529182434","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":"Q1111039$2ED05F57-B83D-44B5-ADCB-3934C5B20C63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"153542671e6dfb977fef445d658f50f87fbc2c71","datavalue":{"value":{"entity-type":"item","numeric-id":1201747,"id":"Q1201747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb547cbc61b45a806ad94f1f8cd0dda428be26b5","datavalue":{"value":{"amount":"+0.7925087809562683","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":"Q1111039$BDCF8E9F-8953-4782-89CB-0019DB2AAB88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f3d1d96608eb54067bc7c6d34455a9707794d72","datavalue":{"value":{"entity-type":"item","numeric-id":749237,"id":"Q749237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8722d7fda4eaf506121cb6e1c54b2c838fdfe8f2","datavalue":{"value":{"amount":"+0.7793895602226257","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":"Q1111039$76706DC9-9EF7-4485-9D88-E0DA4C3F43CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d334f77ad6caf85f93116358323512fb814ba07","datavalue":{"value":{"entity-type":"item","numeric-id":3795222,"id":"Q3795222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9224bdb204bd184a24a92df638ab4d41128c5410","datavalue":{"value":{"amount":"+0.7744336724281311","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":"Q1111039$C9BD888D-5476-4C06-893E-BC488B2C3BEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78a8a9a8d552efcfe27d60e3a327d7f6ca781c83","datavalue":{"value":{"entity-type":"item","numeric-id":5387800,"id":"Q5387800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2a5e941e585d8bbf8dfd3c8d4acbcb9ff3b9e31","datavalue":{"value":{"amount":"+0.7732478976249695","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":"Q1111039$D687039D-3CC9-4D93-83C2-4FA9C888F2B1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1111039","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1111039"}}}}}