{"entities":{"Q685605":{"pageid":687454,"ns":120,"title":"Item:Q685605","lastrevid":47189173,"modified":"2025-12-31T23:11:02Z","type":"item","id":"Q685605","labels":{"en":{"language":"en","value":"A convex polygon among polygonal obstacle: Placement and high-clearance motion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417470"}},"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":"Q685605$819B015F-58F0-474C-B5F5-B3D7933B11F7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"86baa533ee3a98d9c1e9d44fa1269b54dfa5ab6e","datavalue":{"value":{"text":"A convex polygon among polygonal obstacle: Placement and high-clearance motion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685605$C104C04F-7FA3-420D-A93F-C14FE68BCEE0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"17e95167fac2d5abe6813002cf7e751856a2b45c","datavalue":{"value":"0779.68087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685605$39280B55-048B-4691-A505-A81FD87E31DF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0d20e0a71087359143aef249c2b1309fcb95233f","datavalue":{"value":"10.1016/0925-7721(93)90001-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685605$155AD957-304B-4EB6-8A20-6C195C9E42B8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"36f72dc458dbb68417eed24578c25b37631aa961","datavalue":{"value":{"entity-type":"item","numeric-id":598236,"id":"Q598236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$FC47D247-A602-4C56-B352-31ADD22E5EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b2c0b8ea3e503bcb4f4d324a3e772d994cca534","datavalue":{"value":{"entity-type":"item","numeric-id":293193,"id":"Q293193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$18963FFB-830C-4508-8DF4-E8340F3D62FA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$E5908F28-DA25-43CB-8863-75CA11DEC881","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"68b724eb687dbe57c6756b615ba860966fd43d36","datavalue":{"value":{"time":"+1994-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685605$A7A68CF5-E46B-44AD-9364-49DC4942D4D6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ef4a5a9892a3beb2be7d4899fd1f233b8485ad62","datavalue":{"value":"Given a convex polygon \\(P\\) and an environment consisting of polygonal obstacles, we find the placement for the largest similar copy of \\(P\\) that does not intersect any of the obstacles. Allowing translation, rotation, and change-of-size, our method combines a new notion of Delaunay triangulation for points and edges with the well-known functions based on Davenport-Schinzel sequences, producing an almost quadratic algorithm for the problem. Namely, if \\(P\\) is a convex \\(k\\)-gon and if \\(Q\\) has \\(n\\) corners and edges then we can find the placement of the largest similar copy of \\(P\\) in the environment \\(Q\\) in time \\(O(k^ 4n\\lambda_ 3(n)\\log n)\\), where \\(\\lambda_ 3\\) is one of the almost-linear functions related to Davenport-Schinzel sequences. Based on our complexity analysis of the placement problem, we develop a high-clearance motion planning technique for a convex polygonal object moving among polygonal obstacles in the plane, allowing both rotation and translation (general motion). Given a \\(k\\)-sided convex polygonal object \\(P\\), a set of polygonal obstacles with \\(n\\) corners and edges, and given initial and final positions for \\(P\\), the time needed to determine a high-clearance, obstacle-avoiding path for \\(P\\) is \\(O(k^ 4n\\lambda_ 3(n)\\log n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q685605$3BDD0329-88E3-4B2B-AD19-BA2A54C69347","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685605$F050C604-9E25-4C6F-910D-2B42D8913030","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685605$4E8110F1-A02A-4605-8C53-C23983BA2758","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bfb9821f00280505250e7a5dbe2425b9bbd5f040","datavalue":{"value":"417470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685605$B4E6ACA6-97C1-4055-93A7-BD3DD1118B46","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ff4036d2cb769e1456b0ee6008ee986ba76bb27","datavalue":{"value":"edge Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q685605$A5590608-4EA2-4934-B539-0B9D9C2C369C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"daca19087e72573efbef0bf0b7aac34a677eabe5","datavalue":{"value":"edge Delaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q685605$F2E83AE6-E6DB-457B-B7BA-536114DA7B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7638652825683bfe9fbdcacf89d6fa0bde32cc7a","datavalue":{"value":"convex polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q685605$47CC7690-C7B5-498A-B3C1-0DB141AAD848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"900572492ff0b9c514cba808fa7fe3539b0c1cb0","datavalue":{"value":"Davenport-Schinzel sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q685605$3A5B006A-DB67-482C-869B-707829F5B430","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":"Q685605$6D734D08-FC10-4FE5-BCFC-9A8C4D57F19B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7203981c7aad6e3cc11229b68ca8a6081557c6af","datavalue":{"value":{"entity-type":"item","numeric-id":3787492,"id":"Q3787492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$FAC31DDB-47A0-4AF4-B578-D4C9F8041A5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ad6a447ed415489e99550ada5d106e44638f0b1","datavalue":{"value":{"entity-type":"item","numeric-id":911595,"id":"Q911595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$28F29583-34B7-437C-ABC3-100214424E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a576cd28ada66a4d90fff61b4f2556c5be21d817","datavalue":{"value":{"entity-type":"item","numeric-id":1071526,"id":"Q1071526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$61D35319-B72E-41AF-BDF7-D433484098F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98686b48b8c2e08b48821e02e53348b40525712c","datavalue":{"value":{"entity-type":"item","numeric-id":1115601,"id":"Q1115601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$EF71DDA6-0FE6-49E5-8F7A-9A3D7A71583B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1199d12a950df4560a76c40a4a6d0f4360c36a30","datavalue":{"value":{"entity-type":"item","numeric-id":3687711,"id":"Q3687711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$91F2F5D6-DE41-48A6-8C2C-FF93EF58E7F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99114b1bd38a031039ee6a9bed0217048b0b5658","datavalue":{"value":{"entity-type":"item","numeric-id":1101224,"id":"Q1101224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$8AE5AF51-8174-4061-93CE-2300AD71767D","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":"Q685605$D60FB13E-66B5-4B42-95D2-BA5C143CC7DF","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":"Q685605$682C247B-B176-4B25-A238-D89F45ACE242","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":"Q685605$DE83C4B8-6F87-4319-B98F-4D662F19EB70","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":"Q685605$AEE11921-3F2F-4CD9-A0A5-7DF29E82A3EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cceec15e0bf6f1544f3e1864012ec31a05ee6eb","datavalue":{"value":{"entity-type":"item","numeric-id":1078807,"id":"Q1078807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$F66FDB18-02AE-4A19-952A-B71D9E839B3E","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":"Q685605$6B1CC2AB-A3F3-4EDD-9146-62E1325ABBDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb9ce8a84b3ae2d93c43f6026772aa9721f7d7b1","datavalue":{"value":{"entity-type":"item","numeric-id":1821354,"id":"Q1821354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$026EE5DF-5D4D-4993-AFCF-4DE4AC7EBBD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c31401b27b59ab93330106eaaae9b471a83d429","datavalue":{"value":{"entity-type":"item","numeric-id":3736451,"id":"Q3736451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$A7E1639E-F7E2-4630-AA12-E282074CB3A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dca04568c4dfb5342a35fa8c21257c511b7967fb","datavalue":{"value":{"entity-type":"item","numeric-id":1094871,"id":"Q1094871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$51F7F091-15AF-46F5-A390-3647F016F77B","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":"Q685605$1DEC907B-35CE-444D-8A90-F49709960866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b2d4c35681c657135b1459d72a927361adde702","datavalue":{"value":{"entity-type":"item","numeric-id":1093370,"id":"Q1093370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685605$7EEA48C4-D847-44A9-99D8-19329ACE8E67","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26daba1de69febb926eb86a87a1bbd5b970821cf","datavalue":{"value":{"entity-type":"item","numeric-id":1302036,"id":"Q1302036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5814391769c3e0b8e48d376c21c6bfd2597795c","datavalue":{"value":{"amount":"+0.8564678430557251","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":"Q685605$926D26DE-F457-4221-9953-4BA9083DE2D3","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":"ab1e70fdc41312e64d9fc1b79fb50545ffa522dc","datavalue":{"value":{"amount":"+0.7926909923553467","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":"Q685605$9FFE7D4C-B557-4663-A8A9-8D99CEE46190","rank":"normal"},{"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":"026200abe9ac4dd94bbebed51b33d8693a5ff544","datavalue":{"value":{"amount":"+0.7501136660575867","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":"Q685605$53553C34-1E7B-4DDF-A99F-24F58E61EE3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a1a367c4c017474bf721fa5c5022c4e1de459b7","datavalue":{"value":{"entity-type":"item","numeric-id":4575663,"id":"Q4575663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4451e418b2b20febb938055c7c942ba1e72cee44","datavalue":{"value":{"amount":"+0.7493274211883545","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":"Q685605$5D6A5E4F-1B58-4026-AC92-8420D4E4F2FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"436e9c465040efb4057022766f67f730f1496ffa","datavalue":{"value":{"entity-type":"item","numeric-id":1380791,"id":"Q1380791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbb5f698fd69d6c262f8df1d70cd134b0d1ca077","datavalue":{"value":{"amount":"+0.7486558556556702","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":"Q685605$423B7FA0-3FBD-4629-B409-7121759AD06F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685605","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685605"}}}}}