{"entities":{"Q1198024":{"pageid":1208773,"ns":120,"title":"Item:Q1198024","lastrevid":47107774,"modified":"2025-12-31T17:05:42Z","type":"item","id":"Q1198024","labels":{"en":{"language":"en","value":"Optimal time bounds for some proximity problems in the plane"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92093"}},"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":"Q1198024$A1567925-222B-44B7-A5F2-B7A971C07394","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f081a9539ef1b25008f348f4e1affb84be80a82c","datavalue":{"value":{"text":"Optimal time bounds for some proximity problems in the plane","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198024$98C72016-2E85-4226-A07A-573523BAF7C0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"442301c3165ccdefa2d1585682caf1cd66342901","datavalue":{"value":"0761.68093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198024$97C8F695-A76E-489A-B62A-F71BFC6ED93A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"58c277cb2c73976c8ba697b7951ad0a3e74e331d","datavalue":{"value":"10.1016/0020-0190(92)90133-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198024$E60DC06A-044D-4BFC-82E2-F32736EBCCEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"64a5e02458a327e7b854a0a51ea17759c9e5c450","datavalue":{"value":{"entity-type":"item","numeric-id":834913,"id":"Q834913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$5742E5A6-A756-4D70-B1E9-8A76E6F14D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b0fb0f2c86e93cd39417ea5519157255e289364","datavalue":{"value":{"entity-type":"item","numeric-id":222782,"id":"Q222782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$7FE244B1-5DD3-44EC-9B5E-810BD9DDF5A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"74ab5fd86840fc5ffff602487c6ddd935d8a77ea","datavalue":{"value":{"entity-type":"item","numeric-id":287182,"id":"Q287182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$81022290-8530-4C01-A030-84B2A898F438","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a06f7d76e1dbfa89a80e5d40561052d9e137ca58","datavalue":{"value":{"entity-type":"item","numeric-id":242843,"id":"Q242843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$8A2D6D82-E62E-439C-A171-6BF84CF6B379","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":"Q1198024$4F288485-EA88-4A01-B651-B2A1717424A7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198024$356F99FF-C840-4C34-9AFA-DF1BA5BE2161","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"45182f3c08d8382dcb30b6d5ff717bbfd6978b87","datavalue":{"value":"The \\(\\Omega(n\\log n)\\)-time lower bound (under algebraic decision tree computation model) for the problem of finding the closest pair for the sequence of vertices of a monotone or star-shaped polygon is proven. This matches with the known upper bound for simple polygons. The proof is by reduction from the integer element uniqueness problem.   Another main result is the \\(0(n\\log n)\\) algorithm for the following closeness problem. Given a collection of point sets with \\(n\\) points in total, for each point find the closest one but not from the same set.   Additionally, a simple \\(0(n)\\) algorithm is presented for the element uniqueness problem under the RAM model, to demonstrate its difference from the ADT model.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198024$F918495E-61C3-4FB5-9236-861AF047CE7C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"257d0165052e5019ac8fd49a93c7aebbdcc243c0","datavalue":{"value":{"entity-type":"item","numeric-id":751866,"id":"Q751866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$57E517C8-8238-4099-A773-B735808965B7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198024$D8A5CE49-3065-481E-BAE6-54D024B1B59F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198024$1C730D8F-B90B-47BC-B859-F698FC15A3F4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c0ce7b6285469c7e8f6c0bda1b9c5044fa30a317","datavalue":{"value":"92093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198024$E42A0874-E53E-426B-A3A9-B5DFC0D0F9FC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fb5f0e9e71709dc853e837415045aef8a51c583","datavalue":{"value":"proximity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198024$13101DD8-5371-4EE8-80D0-88451C8A81AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198024$5423F787-6EBF-49F6-B113-E5C02F74A76D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dca89b4a5f675108e2ba77a7bb316802feca0b21","datavalue":{"value":"closest pair","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198024$68B4F443-ADE5-43E4-91C4-4F8D2B7A8C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b198546508854bcc521c452e3e0681a16812ba9","datavalue":{"value":"polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198024$5DAA06A2-885C-4463-AED1-B0CA06886651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ccf916c7509c9dd96ad1aba4033c42e10decb7f","datavalue":{"value":"integer element uniqueness problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198024$6D12C917-2DD0-41C7-976D-BCA4F981A8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b328493df3ded101c06c1fc30203c9dec5f6ebae","datavalue":{"value":"point sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198024$134242E5-AAAD-4BED-98EC-FF2B8C26184F","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":"Q1198024$8C3350A8-8F9F-4E36-861D-B61A5226E906","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$E44288CD-7119-4E43-921E-0F367C7DF35F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e78add1d8b013583dbc6de9c2424cecf91acefae","datavalue":{"value":{"entity-type":"item","numeric-id":1101223,"id":"Q1101223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$D6242DF5-84DB-4A94-BB60-748002375485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab0801fac3bfdca64a96207d57004f035ca6527e","datavalue":{"value":{"entity-type":"item","numeric-id":4028879,"id":"Q4028879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$3D348833-B321-46D5-A677-8152C8769B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49b7557b673baecad0ec34997bfbd86b0c9130bd","datavalue":{"value":{"entity-type":"item","numeric-id":4140384,"id":"Q4140384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$FCF47FA9-5667-47E1-8614-25A7D28F3796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$0214E20A-A47F-4116-BF83-3EF760B8462A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"add3ba7c961dbac8a0bad942908ab7ee33c9a780","datavalue":{"value":{"entity-type":"item","numeric-id":5896232,"id":"Q5896232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$AFED1720-A040-4981-BFC6-917C2F5055E5","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":"Q1198024$53CDAF08-153B-4313-BBC2-C8496B753E06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab9002c6ee03c89bc48bc9e3b89404864edba99f","datavalue":{"value":{"entity-type":"item","numeric-id":1250433,"id":"Q1250433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$3D2E4657-714D-455E-AC78-39732E3A7753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a56dff4b0084f9c52d53e29b65d1b0a3e2cf0a5d","datavalue":{"value":{"entity-type":"item","numeric-id":3776623,"id":"Q3776623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$F93316CD-9052-4D12-ACEF-597FFD9ED9A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e583938929e7d2c63f5f6d8fed7581a322ce98a","datavalue":{"value":{"entity-type":"item","numeric-id":1134524,"id":"Q1134524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$54E05E1E-2BC7-4FAD-BFB4-92A4372BBDFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$A4BCC36B-D965-41BD-A1F7-F46E65D7F31E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b0ea9107292543579c21ea0c0cb14a4149357c5","datavalue":{"value":{"entity-type":"item","numeric-id":3716336,"id":"Q3716336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198024$B6284F37-81E7-4BD4-9D83-B2F4DF1E05A6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"91c5003e2f260c3262782d0e161160014c3051d3","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90133-g","type":"string"},"datatype":"url"},"type":"statement","id":"Q1198024$1E8B864F-F81D-4A6D-AE17-93CA15565618","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ee84cb3bdaf981905d616700190bc027ca49e5ef","datavalue":{"value":"W2034144081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198024$FE448AC2-40F2-4D37-B1D7-22C3CE152A0C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f373f467870a71424fa98929593c73e567eb8267","datavalue":{"value":{"entity-type":"item","numeric-id":4945521,"id":"Q4945521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7257c45a2cc2b694f63a2f5b6036ce7eb3ffd1d5","datavalue":{"value":{"amount":"+0.7993021011352539","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":"Q1198024$881873E3-C6E3-4C90-9335-49B49F3976F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e635807ea5acbde1bcf1515442aa0576702eeece","datavalue":{"value":{"entity-type":"item","numeric-id":2489537,"id":"Q2489537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f067857603e794f5e77bc58c8c4910a455ebf43","datavalue":{"value":{"amount":"+0.7636995315551758","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":"Q1198024$9836F2E5-E42F-4186-B80F-4608F65D070A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cca8d4217b40e74f97f71f8c0923f606eb3d3d1","datavalue":{"value":{"entity-type":"item","numeric-id":4828970,"id":"Q4828970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"181d411b8a3de18a68a466f35abb03af8de48f35","datavalue":{"value":{"amount":"+0.7585179805755615","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":"Q1198024$6360B408-4BEA-43CA-A6D3-3703E3595E72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0789c68d68703c796900de5285a32bf96469a8f","datavalue":{"value":{"entity-type":"item","numeric-id":4818603,"id":"Q4818603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32b8dfc3480a0f00e25e6624fce9f8d70edada9a","datavalue":{"value":{"amount":"+0.748957097530365","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":"Q1198024$77468DD3-DB64-4FB3-92C4-01EE293D08D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5aa260ef39a16e7ebc84f081bde890c0a90a66d","datavalue":{"value":{"entity-type":"item","numeric-id":5096784,"id":"Q5096784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a113463fa3970bb00750fa57d2ad94e27e13b7b","datavalue":{"value":{"amount":"+0.7484202980995178","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":"Q1198024$8993CC2A-5B8E-430E-A20E-2DFBB52CD01A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1198024","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1198024"}}}}}