{"entities":{"Q1940703":{"pageid":1951445,"ns":120,"title":"Item:Q1940703","lastrevid":71182764,"modified":"2026-04-13T20:07:10Z","type":"item","id":"Q1940703","labels":{"en":{"language":"en","value":"Convex hull of points lying on lines in \\(O(n\\log n)\\) time after preprocessing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6142832"}},"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":"Q1940703$2E8C6407-74A2-4626-AE8E-1DD79EC92167","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"68cda34b1fac6edd88f415c64e0199d022d107e4","datavalue":{"value":{"text":"Convex hull of points lying on lines in \\(O(n\\log n)\\) time after preprocessing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1940703$7964DFE2-1B54-422D-855E-22A588611B5F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"54b2fed6088e27f6621c429837fa2e34770ae24a","datavalue":{"value":"1262.65031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940703$6EAEC25E-397A-48BA-8A9E-416EF617ED4C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1801a38b0aa56774cf093edd7f94dd73d051e975","datavalue":{"value":{"entity-type":"item","numeric-id":407568,"id":"Q407568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1940703$8F163C0D-EDBD-4936-A54C-E76B1E03C395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8402804d132105b21de1e92dcac2c27db3304a01","datavalue":{"value":{"entity-type":"item","numeric-id":312141,"id":"Q312141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1940703$2D4CFB72-F8FE-4264-8DF2-5C6A9CE49C66","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":"Q1940703$8780CCF3-3F42-42B1-94D7-84EC83A5433E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3b19acb3e8c7a2662dfca6a9069f307fd3945628","datavalue":{"value":{"time":"+2013-03-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1940703$7FE6A8C8-F7FD-46FB-BA75-24354CB2A1F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cabdab4e758c52d4c6d290f378552c80acd61204","datavalue":{"value":"Given a set of planar regions, each of which represents an estimate about an input point, and the exact coordinates of the points arrive some time later and need to be processed quickly. Under certain assumption, the authors show that one can preprocess the input lines \\(L\\) such that given any set \\(P\\) of points, each of which lies on a distinct line of \\(L\\), the corresponding convex hull can be computed in expected time \\(O(n \\alpha (n) )\\), where \\(\\alpha (.)\\) is the inverse Ackermann function [\\textit{J. Basch} et al., J. Algorithms 31, No. 1, 1--28 (1999; Zbl 0928.68034)]. The authors' data structure has quadratic preprocessing time and storage and the convex hull algorithm is based on a batched randomized incremental construction similar to Seidel's tracing technique [\\textit{R. Seidel}, Comput. Geom. 1, No. 1, 51--64 (1991; Zbl 0733.68092)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940703$882B1E78-13A1-44CA-B6F7-F534DB6BF167","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940703$024D1C4D-A6C9-4546-99C7-97D304170B9C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"510fe2d267d90567e65d3a39196e25bf0449f753","datavalue":{"value":"6142832","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940703$E2B774E6-253D-47CF-8EC8-AB8F8EAA66DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87bea622265019116192ed0ea037fb12b275ddd9","datavalue":{"value":"data imprecision","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940703$F68E9DDD-FDA3-4E9D-908A-CEB08DD13FB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940703$80607ACB-EC25-4C14-A60C-FECA259B1301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89e4e5e22072a5ac16aea0873cf43187d82b455c","datavalue":{"value":"planar arrangements","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940703$EDFF08CD-CFA0-45CB-86C2-806400A5DDDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58b187afe44b62e3e6d298a06b128d676f926241","datavalue":{"value":"geometric data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940703$F63BC4FC-9558-4C24-9D4C-93B534063834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940703$36E74A86-A7CA-41E8-AB52-D8D9C2C4F48E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"956419f6fd71b8dac027f33d0ad5be15c64817eb","datavalue":{"value":{"entity-type":"item","numeric-id":182524,"id":"Q182524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1940703$6B7AEEEF-8C62-4363-AFE1-B73ECB487A53","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":"Q1940703$EB312817-55DB-450A-BC90-E8C9EDFC554C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4cf176aea2440370e57d6883a07fcb1dd6755be8","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2012.03.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q1940703$2C05A020-C25D-475B-BE7E-0C6D1C7993FE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b267a5dfb6d8f23f7cd41ebb82635be5fd84ab58","datavalue":{"value":"W1589450195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940703$54926F9C-8835-4215-B44A-C30BA1761DCF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0970cc48fb7295ed4a5f0bba19e2eb90bd43405b","datavalue":{"value":"10.1016/J.COMGEO.2012.03.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940703$F1BAC6F1-8D1B-4973-A243-DD07475408C2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8623774cccb1a030d6e48ce43bfe59ccd8aa2b93","datavalue":{"value":{"entity-type":"item","numeric-id":5404402,"id":"Q5404402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b90411b9831dc412f808c35dcc8ce943c504f25a","datavalue":{"value":{"amount":"+0.9540913701057434","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":"Q1940703$7FFC24B1-6779-4CB8-B03D-56CF911ED6C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"384532a9324a2f5c678084474461277d6f887494","datavalue":{"value":{"entity-type":"item","numeric-id":2930268,"id":"Q2930268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"190584b473c0709f42941415d9c9e9b10c4842de","datavalue":{"value":{"amount":"+0.8109107613563538","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":"Q1940703$CDDB97EE-E76A-444B-83A1-CED3A9971924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"883394d48cfd5dde5aebc654cb233487258915eb","datavalue":{"value":{"entity-type":"item","numeric-id":1803271,"id":"Q1803271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d83c54a92a4802e17c5a36213cc7813a7705b968","datavalue":{"value":{"amount":"+0.8008825778961182","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":"Q1940703$C0CAA0A1-BD2C-4370-A454-BD365DC05E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39054228c02cbe29d40af50e9a8ee7f76cda1a36","datavalue":{"value":{"entity-type":"item","numeric-id":4696647,"id":"Q4696647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1d9603aaadd15dbbef0461a09e7ae4fbf2468e5","datavalue":{"value":{"amount":"+0.797276496887207","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":"Q1940703$F59E1A0F-2088-4258-BA6F-74070E089D36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8aa5ed23c61011a88283370ca42d8f71e70596d4","datavalue":{"value":{"entity-type":"item","numeric-id":1816463,"id":"Q1816463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31f75ecf6c89ab065e2f016020eab7a012126236","datavalue":{"value":{"amount":"+0.7791248559951782","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":"Q1940703$6F6CFC5E-3797-4339-9473-2AC0F240F89B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Convex hull of points lying on lines in \\(O(n\\log n)\\) time after preprocessing","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Convex_hull_of_points_lying_on_lines_in_%5C(O(n%5Clog_n)%5C)_time_after_preprocessing"}}}}}