{"entities":{"Q1104091":{"pageid":1114843,"ns":120,"title":"Item:Q1104091","lastrevid":49176814,"modified":"2026-01-06T17:22:51Z","type":"item","id":"Q1104091","labels":{"en":{"language":"en","value":"Lower bounds on moving a ladder in two and three dimensions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4055045"}},"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":"Q1104091$C2A8BF30-27AD-412C-8908-FB977E8C9806","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d06f6a46198b8dcf33885dc00a52b975c2be909","datavalue":{"value":{"text":"Lower bounds on moving a ladder in two and three dimensions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104091$00813B8F-210A-4514-9395-237E8CBD421D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6a4ffc0c9d1a0d009835a22cb220968b5137892","datavalue":{"value":"0646.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104091$A3DEF0BE-F0DE-428B-9CA8-B91725C3612B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"11ef3bfe1e5fb7129b743ec10c96baad2e7ba76d","datavalue":{"value":"10.1007/BF02187908","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104091$2A91E58D-06BF-4E2D-BD95-1E2278652D97","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe9025021cb9475b024f154baa66da1c6faff8ea","datavalue":{"value":{"entity-type":"item","numeric-id":1104090,"id":"Q1104090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104091$FDA2CB90-FE44-4DCA-BB02-FD31C2E07E92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"931993058e8741daaf0799b9497e3ca481154652","datavalue":{"value":{"entity-type":"item","numeric-id":223096,"id":"Q223096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104091$56C9E694-8E9E-4120-AF6F-574646434C5E","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":"Q1104091$A83EBED0-1A83-4D83-A891-0F52660B78A7","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":"Q1104091$8695BA61-FA25-4A85-ACA8-FA21A6D46C8A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4bcdcc18344948d37efc2ef495d2481fefd3582a","datavalue":{"value":"https://eudml.org/doc/131046","type":"string"},"datatype":"url"},"type":"statement","id":"Q1104091$1C5D65CC-2A42-4FED-A836-BEB421FA0592","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e2113fc4be452f49e5adc7a4b821e6798bd4681e","datavalue":{"value":"It is shown that \\(\\Omega (n^ 2)\\) distinct moves may be necessary to move a line segment (a ``ladder'') in the plane from an initial to a final position in the presence of polygonal obstacles of a total of n vertices, and that \\(\\Omega (n^ 4)\\) moves may be necessary for the same problem in three dimensions. These two results establish lower bounds on algorithms that solve the motion-planning problems by listing the moves of the ladder. The best upper bounds known are \\(O(n^ 2 \\log n)\\) in two dimensions, and \\(O(n^ 5 \\log n)\\) in three dimensions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104091$A338F408-31DF-417B-95CF-964F8CFF71C3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104091$8F3F25C8-F041-43F4-A6B6-3C19293A00F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104091$B7A92307-FFA4-40E4-B9C9-64C2F59F1DAD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fdb37b4cb9fb959cddbce59229746e3775056d15","datavalue":{"value":"4055045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104091$3EA1A6A6-D5A9-45D4-8E43-737096289C25","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104091$DFE11290-E7F7-4DF7-AA65-F8521CB1C5C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1a0d8556956f328dc85d4908eb7668485fe869f","datavalue":{"value":"motion-planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104091$159F57E9-FABB-4D10-9D66-4143BEC14B2F","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":"Q1104091$FC85DCC3-1F35-4F2C-B931-493A70E1A979","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0bb2a78ba34e8728e91d77da2bf6df4e36bb56c","datavalue":{"value":{"entity-type":"item","numeric-id":3740283,"id":"Q3740283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104091$0DBD108D-F8B3-44A2-A049-C6B1BBE59C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f3a00c41c8365dadba43270184930d03ceda008","datavalue":{"value":{"entity-type":"item","numeric-id":3217189,"id":"Q3217189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104091$D2DC344A-D94E-4B5B-83CC-40789FDC2115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ab148c24a00612e089d62da7acf29e35d25d11e","datavalue":{"value":{"entity-type":"item","numeric-id":3217190,"id":"Q3217190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104091$71014267-4014-41DE-9933-5D5E14642C95","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":"Q1104091$E7D1311D-052C-40C6-861D-C0FF341B105E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4acdc8b2eb596c13997a01ae4761413fd9036cfc","datavalue":{"value":"W2064867966","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104091$0578737F-53E5-4FE1-980A-F845E87B2C55","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"638ed4e2b6924c8c4dedfacba14b3bb89fdbdf3f","datavalue":{"value":{"entity-type":"item","numeric-id":3785936,"id":"Q3785936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e720cd7029a752db2d5fb84f66c2defafce3b65","datavalue":{"value":{"amount":"+0.8655723929405212","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":"Q1104091$A942EB05-8105-42DE-B1B3-7B38E43F1BE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6613a89a1b34280cc2c3b9cfec8f5e798cb2c48e","datavalue":{"value":{"entity-type":"item","numeric-id":1102109,"id":"Q1102109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b99486285dcefa5423c47b7cd51a082b4ceb4678","datavalue":{"value":{"amount":"+0.8451175689697266","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":"Q1104091$F9F17CE0-F572-47C1-AB1D-890BC7334704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15e0d76c8635b230109ab61ce3e22686cec997f6","datavalue":{"value":{"entity-type":"item","numeric-id":1822971,"id":"Q1822971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a90c34db0485d7387f42cf1e63984f48ad124b96","datavalue":{"value":{"amount":"+0.8329789638519287","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":"Q1104091$2C2C1C5B-74E0-48F7-A61A-C255C12AFE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e45bc56b487e747348b4b1f6b693b2314278e3f5","datavalue":{"value":{"entity-type":"item","numeric-id":1098643,"id":"Q1098643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b1c708fecd3c55778bb59cdd489edb61ddc82f5","datavalue":{"value":{"amount":"+0.8176323175430298","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":"Q1104091$3C1035F6-7F0A-4E4D-8A72-EE74DE68DD6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5ef37e927cd945054fdec13852b418cd4cd1089","datavalue":{"value":{"entity-type":"item","numeric-id":3736451,"id":"Q3736451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fd8942881be794553a73c3a7e11830f10245516","datavalue":{"value":{"amount":"+0.7971614003181458","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":"Q1104091$33DFF1CD-684A-4D81-BE37-51454021E4DD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1104091","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1104091"}}}}}