{"entities":{"Q1201747":{"pageid":1212496,"ns":120,"title":"Item:Q1201747","lastrevid":55897966,"modified":"2026-02-20T23:07:36Z","type":"item","id":"Q1201747","labels":{"en":{"language":"en","value":"Minimum-link paths among obstacles in the plane"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 98405"}},"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":"Q1201747$B9B455AC-A01C-4E2B-A250-064E0FF0F163","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"460d19ba7fbd70a1318bc53c719639bea5f95ef5","datavalue":{"value":{"text":"Minimum-link paths among obstacles in the plane","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1201747$BFCCC97C-07C0-4E97-81BC-97C634BB38FC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"95faef3ccb66a929e896f40ada8faa5d8bb6ca5f","datavalue":{"value":"0788.68144","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201747$6D8DF989-5B21-4D42-A22E-F72EC3048D9B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"04941c8f13cd7bef2f8e7aa0e69e8e5c6db0ffe6","datavalue":{"value":"10.1007/BF01758855","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201747$FC377752-B58E-4007-8B10-3044B21E0E3C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"58051942065352f1019453b7eb1d17c25a542cb8","datavalue":{"value":{"entity-type":"item","numeric-id":244519,"id":"Q244519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$B95849BD-6BB1-4CAE-BC91-EB9E57FCD69F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fa460b1cc6be19b3913930654284acc6390913c","datavalue":{"value":{"entity-type":"item","numeric-id":170472,"id":"Q170472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$08C89AB5-19B9-4B97-ACDE-FBB46189F1F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a99c5b7728e1965ef01019ed8fae6583a2f22e4","datavalue":{"value":{"entity-type":"item","numeric-id":170010,"id":"Q170010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$1CF2F6E0-5FFC-4144-880F-28FA598E2B89","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":"Q1201747$F59EF7FD-E65D-4D33-A166-5117C836A597","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":"Q1201747$79DC40ED-D186-4372-8240-B2505AC26E49","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"053fef85df6e311f400c422681c3174047ef001c","datavalue":{"value":"Link distance between two points in the plane is defined as the minimum number of edges needed for their interconnection avoiding intersection with prescribing simple-polygonal obstacles. The motivation comes from robot motion planning where the aim is to minimize the number of path bends. The authors developed an algorithm of \\(O(E \\alpha(n) \\log^ 2n)\\) time complexity, where \\(E\\) is the size of corresponding visibility graph, and \\(\\alpha(n)\\) is the inverse of Ackermann's function. The lower bound of order \\(\\Omega(n \\log n)\\) is established. Related results are also discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201747$00CD7CA7-E093-4E54-9AED-55EABE6A7A7D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201747$8BF2AFFD-5809-4F81-B466-C73756B70333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201747$751C2EAA-CDAE-4DBA-8470-ADAD15C3B482","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6e0faa61c47c82207f6cf06e6f3d08f00860a843","datavalue":{"value":"98405","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201747$20CBA253-CCC4-41C7-8827-B80C17EB39BA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201747$1B95BC8A-3313-4F1F-8C25-61C4E9F015D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0a55c2736e925d8ca716adc60907eb59add4cf6","datavalue":{"value":"link distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201747$456CD350-1F7F-48D0-B456-9CDD0E2CA1A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3c4174a5d716f293c7527ce1cefdfb920908bc","datavalue":{"value":"motion planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201747$B5522D79-638D-4EDE-99B5-FF9605AC7F84","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"532bbaac3e370e50bd6ddecca89db5cad8ecea04","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$24AB3C11-6F56-4CA8-BA05-1DB4F68D9E0E","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":"Q1201747$D370054B-F12A-4094-8EFB-25430FACFBC2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1527977d1e97f551ee80e9595c567d4fb5b3ce20","datavalue":{"value":{"entity-type":"item","numeric-id":1176324,"id":"Q1176324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$F2DC13A6-5CB1-43A7-887D-BBFA4DC7C73C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e12a4c19b93464eaac5fd037ddf3a6db66f342dd","datavalue":{"value":{"entity-type":"item","numeric-id":4302817,"id":"Q4302817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$56FC8D36-459C-4F14-94BE-024F2580FF12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc63a64f5b65afa256a94cce3be1f286bfc227dd","datavalue":{"value":{"entity-type":"item","numeric-id":5096146,"id":"Q5096146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$EC3D68A7-18CB-4CEC-962A-6FDFAF979A08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"164b9b0148fc4f277270164e33d12ec61f28a7e1","datavalue":{"value":{"entity-type":"item","numeric-id":1111039,"id":"Q1111039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$1A250C15-59FB-454E-AA82-E807EBF8B2B4","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":"Q1201747$B152B120-A865-4B8B-9B0A-DD28CDCB1C73","rank":"normal"},{"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":"Q1201747$9B061667-7882-483F-86C7-38808ADE2EF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff1af2b4b0acfb50ca62ddd7ca7021cc3edcb47","datavalue":{"value":{"entity-type":"item","numeric-id":3910036,"id":"Q3910036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$2925A61F-A4A1-4442-A8EE-712066354E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b32de81f138bfd0051adfbd8bd15bcb529446c0","datavalue":{"value":{"entity-type":"item","numeric-id":3982713,"id":"Q3982713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$58CF8831-7EA4-408C-BB48-AE9C561E8D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c368a550cf5b4e92a6d4f0e58d9ca1eb20b223cd","datavalue":{"value":{"entity-type":"item","numeric-id":1097884,"id":"Q1097884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$DB5549E6-67A9-4B24-86B1-96AD75332F3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a54274ce572d3c34835d187957120beffafc780","datavalue":{"value":{"entity-type":"item","numeric-id":1102120,"id":"Q1102120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$9AE9AC9D-C7DF-4CE8-A8CC-05C13AEFA237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74caa8dd26dc163a670e2aae9e70cc7322d01346","datavalue":{"value":{"entity-type":"item","numeric-id":3315016,"id":"Q3315016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$19A535F9-51A6-4D7F-90F5-A5EBFBA741C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d9f4c44af503a85955b4792a2514c09bdc5c3e0","datavalue":{"value":{"entity-type":"item","numeric-id":1104086,"id":"Q1104086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$6DF9CF43-2B75-4336-ABC0-24F41DA6D8B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08d2ef5f4599950963025b2804feb51599b58d30","datavalue":{"value":{"entity-type":"item","numeric-id":1201747,"id":"Q1201747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$1DA06A34-B6E1-465D-BBAB-EC08DABE68D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45ce96ee513514e815725e851b3daeaea5391a2f","datavalue":{"value":{"entity-type":"item","numeric-id":3026389,"id":"Q3026389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201747$0234284B-C7B9-406F-8375-698B2C65F895","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"025bf1cbeea6b90c91933dde881995dc80b3883b","datavalue":{"value":{"entity-type":"item","numeric-id":2123290,"id":"Q2123290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20e8d8f1d7ed6204c5ef25bdfb7f12e2f1c9d390","datavalue":{"value":{"amount":"+0.8392478823661804","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":"Q1201747$57447868-4645-4E48-9D26-61E161E9CE5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18251c17ad06bcf072ce31bd7e60048e4364634d","datavalue":{"value":{"entity-type":"item","numeric-id":4945513,"id":"Q4945513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"035837868ac30633986d87d413a402275c3fdf8d","datavalue":{"value":{"amount":"+0.83612060546875","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":"Q1201747$FF73798D-04D4-45F3-A990-829320FF44A5","rank":"normal"},{"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":"d949797169efbabb5b3cdde08118e78a2e48a07e","datavalue":{"value":{"amount":"+0.824436604976654","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":"Q1201747$4F3C6B8B-A1B6-4070-9018-7ABE82BBEDAD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1201747","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1201747"}}}}}