{"entities":{"Q784485":{"pageid":786334,"ns":120,"title":"Item:Q784485","lastrevid":57157656,"modified":"2026-03-26T20:19:54Z","type":"item","id":"Q784485","labels":{"en":{"language":"en","value":"Minimum-width double-strip and parallelogram annulus"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7226875"}},"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":"Q784485$94549D60-E247-479D-9E2A-00DC93A965FA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f1811e55d5e225497f446db40fab6d217ea75678","datavalue":{"value":{"text":"Minimum-width double-strip and parallelogram annulus","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q784485$2F3DCC0C-3CD2-4BAA-BC75-83842ED226FC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4c0f42547fbdd10bcc2556d7e5e57b848abf9754","datavalue":{"value":"1455.68228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q784485$1E8956D4-BBE0-4E4C-8267-7A2E6D7E8F79","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aad2244a0fac49ecd6eb575ec97eea59fe9c09ce","datavalue":{"value":{"entity-type":"item","numeric-id":283874,"id":"Q283874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$460C7255-67C9-4FE6-9633-B6EDACBB3DD5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$54303D2F-0B73-418D-A7F5-1C78B4059866","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"469d299b05f6ef0db902802d19518b8f861cc702","datavalue":{"value":{"time":"+2020-08-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q784485$903D4BF5-C3E8-44A8-9C96-E4DC38884C31","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c4b577b25153aba8e4946e3324dcea7cce4ed02c","datavalue":{"value":"https://arxiv.org/abs/1911.07504","type":"string"},"datatype":"url"},"type":"statement","id":"Q784485$B7B10033-6F8D-4073-8BA5-7E6AAC7CAEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"97dc54993213ea12305efe27441b67c3284390aa","datavalue":{"value":"https://drops.dagstuhl.de/opus/volltexte/2019/11521/","type":"string"},"datatype":"url"},"type":"statement","id":"Q784485$26B51A86-CCB2-47FC-908D-69D8C1FB9525","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f2470bc9820c2bf9e255b98f1fa0ad4c4100656c","datavalue":{"value":"A planar strip is the closed set of points between two parallel lines, and its width is the (orthogonal) distance between these lines. A double strip is the closure of the difference of an outer strip and an included inner strip, its width being half the difference between both strips' widths. A parallelogram annulus is obtained from two double strips of different orientations by intersecting their outer strips and deleting the interior of the intersected inner strips, its width being the larger of both double strip widths.  Given a set of \\(n\\) points \\(P\\) in the plane and a subset \\(Q\\) of size \\(k\\),  a  minimum-width double strip containing \\(Q\\) with outer strip containing \\(P\\) can be computed in \\(O(n\\log n+kn)\\) time using the geometric dual. With a same complexity one may compute such a minimum-width double strip for all stepwise reduced \\(Q\\) in prespecified order. A minimum-width parallelogram annulus containing \\(P\\) is computable in \\(O(n)\\) time for two fixed orientations, in \\(O(n^2)\\) time for a single fixed orientation, and in \\(O(n^3\\log n)\\) time when both orientations are free.","type":"string"},"datatype":"string"},"type":"statement","id":"Q784485$1469263A-F3DB-4A03-99E4-65CD635B3DCB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$29A87673-81AD-4158-ADD3-E112A6849662","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q784485$2CF95F4B-785A-4E50-88A8-F493B62A6E3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q784485$86F5077A-54C7-49ED-8D74-749E21B747F2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9f0c43f5d567d5cbf72b5a5764142261555f6fd0","datavalue":{"value":"7226875","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q784485$4BCA8650-904C-44EC-9EDC-D4CD96327E8A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56c22d5775221423046cc5c67c2b493cdcf52842","datavalue":{"value":"exact algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q784485$ED12BB0B-93AC-4E62-83EB-EB2A34EA1D77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q784485$C6123959-9300-40E4-8B85-1FC58056D63C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32e3bc82caad8f7c98cede3a2d407b4bf928513e","datavalue":{"value":"arbitrary orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q784485$BB651662-7B96-48B9-8FB1-37F48BABF62A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f73dd776c58bd4cf842257bb41bb89d7890c8874","datavalue":{"value":"two-line center","type":"string"},"datatype":"string"},"type":"statement","id":"Q784485$4F90A6C1-E5B1-459A-8D4A-C47F0281562A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4040078fc73495ce1115ba2fe126fce7a2c71a3","datavalue":{"value":"double-strip","type":"string"},"datatype":"string"},"type":"statement","id":"Q784485$D0CBA0A2-DB2B-4371-B882-43430C520617","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab4c118c367655b38a0c06f9035750a19471a081","datavalue":{"value":"parallelogram annulus","type":"string"},"datatype":"string"},"type":"statement","id":"Q784485$7C400ABE-7078-4A81-9AF7-3021853A2202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5279eeabb222156f13ea12cf903ea5bc3a99af18","datavalue":{"value":"geometric dual","type":"string"},"datatype":"string"},"type":"statement","id":"Q784485$D557BEA9-6E3B-4AA3-909A-34756A296F94","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":"Q784485$AAFB7585-9186-46C6-B48E-35684C17FF6E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"70e83408d6b5c5d95cd70ee31601f4f3049bb0e7","datavalue":{"value":"W2991015355","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q784485$6D2FD82F-E6E5-489F-AFC0-57FB755D65C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6fffda452aa745bf25131b56a0ba54ce76261f2","datavalue":{"value":{"entity-type":"item","numeric-id":1816458,"id":"Q1816458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$494B63FD-FE8F-4F62-B762-517C4F189FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04624a524065d6511323ea8e7d3263d70f5dd847","datavalue":{"value":{"entity-type":"item","numeric-id":4314492,"id":"Q4314492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$7DF95BD8-B318-4EE7-9B4F-C80BFC700763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbf352186c059506229e983b9b94b19e35e3502c","datavalue":{"value":{"entity-type":"item","numeric-id":1705772,"id":"Q1705772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$A1355F86-0692-4798-A901-70AFA96CE74B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6462e8c5c0aea01f2a594c3439645ce7174b0eb2","datavalue":{"value":{"entity-type":"item","numeric-id":4947407,"id":"Q4947407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$23777045-BD1E-4C2C-AD11-88D1D12A4EDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e5eacbc6dd78b48ad4980c433a47cfb107add2","datavalue":{"value":{"entity-type":"item","numeric-id":1265327,"id":"Q1265327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$0BB225D9-0EB1-4EAA-AB1F-D1AF74F9CA24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de413aaef9efed162fb15aea2e26afa8f0b646b3","datavalue":{"value":{"entity-type":"item","numeric-id":833568,"id":"Q833568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$E6B5CFDC-9FE3-46BF-8319-DF2EE8A02ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cb785b1fa00468f72c20fed51d4e390b8834f38","datavalue":{"value":{"entity-type":"item","numeric-id":582095,"id":"Q582095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$4405C362-2F2C-4569-9BAA-84411C41F150","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6885ab94bd355bce42bd5e8356998e647a6282","datavalue":{"value":{"entity-type":"item","numeric-id":5057418,"id":"Q5057418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$88B2454B-30A4-458C-BC53-7F74401CDA50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5c558f32547a054546690b293cc7b4a1d448f64","datavalue":{"value":{"entity-type":"item","numeric-id":388105,"id":"Q388105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$C8510BC8-EF22-4DCC-8D16-717693F0FA35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b3fffbd933a93b2a1e07ea0bac3190d4ff6f0b1","datavalue":{"value":{"entity-type":"item","numeric-id":1186452,"id":"Q1186452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q784485$AB3ECB49-1BED-4488-956C-A12B60E2A830","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"925eb281f2302700dd218f2803a0e42d17669f03","datavalue":{"value":"10.1016/J.TCS.2020.05.045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q784485$9E0CE444-7ED9-4373-B9C3-5407526CC7B9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf64e1a5150ad99708e2d7a6f20cfe499ef235af","datavalue":{"value":{"entity-type":"item","numeric-id":388105,"id":"Q388105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27c4b32752ab0b3c4a5096f893de16d8d0b4531e","datavalue":{"value":{"amount":"+0.8526545763015747","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":"Q784485$27BB2B2B-4D13-4334-83CE-33A88235BB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a3c40a394235755f910d73313d8ca03a04110bd","datavalue":{"value":{"entity-type":"item","numeric-id":3004689,"id":"Q3004689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c43ce4474b78c26a5c8d1f386a90c1d8afbebaf3","datavalue":{"value":{"amount":"+0.8525992631912231","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":"Q784485$8BE9F115-0638-4115-BC31-58270C3DD731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"319f0e035b3f7b37493d73245c5f9cbab2ff7040","datavalue":{"value":{"entity-type":"item","numeric-id":1705772,"id":"Q1705772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18194980cfcfd2e03f1e2e211de5cb1b74ca4109","datavalue":{"value":{"amount":"+0.8327608108520508","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":"Q784485$124D99F8-C8D5-4AE0-A9D5-3417F8F3BB36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dc3dc9089b2b045363330134106e858e46c2aa1","datavalue":{"value":{"entity-type":"item","numeric-id":5915962,"id":"Q5915962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"454654db3884dc8fd8533a08744d0f6e8179d46a","datavalue":{"value":{"amount":"+0.8093929886817932","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":"Q784485$BCB5D20B-99A8-443A-8C3C-9D6FA43698F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2941b55e4c1e23b5341e67164b588759688e12b5","datavalue":{"value":{"entity-type":"item","numeric-id":833568,"id":"Q833568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c48bbdfb57dc430f3c9c4719d4f385858481a64","datavalue":{"value":{"amount":"+0.8079439997673035","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":"Q784485$CA2BC5CA-B35E-4914-B4EA-DB01B2B09B58","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:784485","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:784485"}}}}}