{"entities":{"Q1312190":{"pageid":1322940,"ns":120,"title":"Item:Q1312190","lastrevid":47222314,"modified":"2026-01-01T01:34:29Z","type":"item","id":"Q1312190","labels":{"en":{"language":"en","value":"An optimal convex hull algorithm in any fixed dimension"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 488282"}},"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":"Q1312190$904D9C63-574D-46F6-9DA2-F04EE9A78575","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef80039c849c4fa9292b75b0a3e07d2e75e44671","datavalue":{"value":{"text":"An optimal convex hull algorithm in any fixed dimension","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1312190$FB9C0D36-BBC3-42B5-81A7-9EF433271BB1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0700f4411adadf8f9ff2cafe5e61fd0b1e99d85c","datavalue":{"value":"0786.68091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1312190$12882E78-CC1C-4939-864F-97C57DC10487","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf0e2023c3e95d1a1e126b2bb5426dd2cdee84c5","datavalue":{"value":"10.1007/BF02573985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1312190$2DAAE6AD-81C3-4E66-A117-B3CB76B40388","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ad91bd4a1378a015ef9d0cfb2ca621b16347f71","datavalue":{"value":{"entity-type":"item","numeric-id":525971,"id":"Q525971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$FE404B0B-74FF-433C-A348-70566F81EBFC","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":"Q1312190$9871CE13-FA6C-4D44-A57B-D44BA79DB1A0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1d9914bc6feb5fa01fb9ecfc8e4444ea1144570c","datavalue":{"value":{"time":"+1994-05-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1312190$8AD9EB3D-377F-4A3F-9600-852A58924B1D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8bdef1843dda11467aeed676e11decc59a889f34","datavalue":{"value":"https://eudml.org/doc/131280","type":"string"},"datatype":"url"},"type":"statement","id":"Q1312190$CC25E6C1-2526-4F81-BC16-1DD10AE8246A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6cb389a73cfbc5efae451b9723e7b6e64edb0d42","datavalue":{"value":"This very interesting paper gives a solution to an outstanding problem in computational geometry. The author presents an deterministic algorithm for computing the convex hull of \\(n\\) points in any fixed dimension \\(d\\) in \\(O(n \\log n+n^{\\lfloor d/2 \\rfloor}) \\) time. This algorithm is optimal in the worst case, but it is not output-sensitive. It is an open problem to bring down the complexity for this problem to the lower bound of \\(\\Omega (h+n \\log h)\\), where \\(h\\) is the facial complexity of the hull. The solution of the paper is based on a derandomizing-technique developed by the author. The counterpart of the algorithm given here is a probabilistic incremental method given in a known Las Vegas algorithm with optimal expected time.   The result of the paper seems to be the first example of a successfully derandomized Las Vegas incremental algorithm. The base is a deterministic version of a Monte Carlo integration method, which seems to be useful for other problems also. A by-product of the result is an algorithm for computing the Voronoi diagram of \\(n\\) points in \\(d\\)-space in the same optimal time.   Besides this results the author introduces the following ideas: 1. A scheme for producing ``random-looking''-permutations. 2. An elementary error analysis to cope with faulty calculations in the Raghavan-Spencer method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1312190$55E133ED-E48E-485F-BE9F-C7F9AB6885FD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1312190$B35D848C-3CDD-437F-A9A6-B4BDA088EEFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1312190$6A26FEB3-7900-4958-80FF-E1E4530986AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3e91529a8a08801bafc0325eb71a11714228bfc1","datavalue":{"value":"52A20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1312190$F05DAE03-ED5D-4D46-BA3A-0389F11A7F4D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eafe8e070e524c4022f9dc41e5b56411421ce5ea","datavalue":{"value":"488282","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1312190$4D039291-0817-430F-9C50-B7E8B78F54DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d056cac9e15b28bd6ed5fb852089e201809c814","datavalue":{"value":"random-looking permutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1312190$1687C256-9DDD-48F9-B265-D2E3A89714C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1312190$4D5063B3-7968-42C4-B8C7-A81C9D26D8CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q1312190$AEA850B1-8C52-47A1-8987-8402109E372A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a3b65d97c347258e119852d0d3c504434cd641d","datavalue":{"value":"derandomizing-technique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1312190$5597FA03-BEA0-4227-A5CB-BDAE1A4E17CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d975c8e13006fbe9b4f6c347ea88f3b06e6e4c7","datavalue":{"value":"Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q1312190$F32691A0-9480-4C9B-BF18-9D38C2972C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"708db7122ea19e071bf4a941d28ec4521c28f458","datavalue":{"value":"Raghavan-Spencer method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1312190$92FE8220-FC1F-492D-B29B-97F2B65EF390","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a0a61150ff13b33c94bdd399d6ea42bb3f888585","datavalue":{"value":"Q56070314","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1312190$EED7A70D-4792-436E-98F5-33AC1E2CD8A7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f97401dc38cdab90e116741461a88db9a2626407","datavalue":{"value":{"entity-type":"item","numeric-id":701798,"id":"Q701798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$1DD1F0D7-2C1A-426E-819E-4D802DB7C410","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":"Q1312190$F9484ECA-5F1C-419D-85E2-799CE8DC0DD4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bec7e40eb194f6986a1a59f6d6553215ed9fe3ca","datavalue":{"value":{"entity-type":"item","numeric-id":914373,"id":"Q914373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$BF56F42D-E998-4E26-AD74-FC65B9E04AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9cd35177b9fbbefa725a3537ebfd136511c156e","datavalue":{"value":{"entity-type":"item","numeric-id":1135110,"id":"Q1135110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$5AB40591-9D4E-4F21-8459-8B3E975FBFAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dfe3c278c3ae1ac9d8f6c63326543b8725ea217","datavalue":{"value":{"entity-type":"item","numeric-id":1209837,"id":"Q1209837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$974011D8-7057-4D4A-9815-DA6DCF4D9BA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d44c65f9584e97826a6445e2d0ce1d2234080f","datavalue":{"value":{"entity-type":"item","numeric-id":751816,"id":"Q751816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$97D38E99-D227-4428-A577-61EF25D16A2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58a133ab6015ea81025ee73498a6e75eab721ae9","datavalue":{"value":{"entity-type":"item","numeric-id":1346251,"id":"Q1346251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$5A708BAE-36ED-45AC-A345-F6F4BEC333FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39501951ef662c90673b58c7b95b5797b92c1527","datavalue":{"value":{"entity-type":"item","numeric-id":3796754,"id":"Q3796754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$75678AD7-70F7-42FA-BDFC-60C8F9754DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8853722611c41579d02ebd114c164fbf2e1b547d","datavalue":{"value":{"entity-type":"item","numeric-id":1823685,"id":"Q1823685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$8EF09EC8-19D2-4C9F-A1E9-CBE7C4B78229","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":"Q1312190$51423D8A-87FA-4DAE-BE53-BF62C6BD5C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"750f6d16c6420fa29e521e2e84425ccb3c1aedc5","datavalue":{"value":{"entity-type":"item","numeric-id":1079823,"id":"Q1079823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$E1718E6D-B610-41BA-AF01-9ECF5F2B5496","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b93cbcfe92914798c52148f95cc353b5e256c5a","datavalue":{"value":{"entity-type":"item","numeric-id":2552382,"id":"Q2552382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$B4183D6C-C02B-4B6D-906C-7D9C0B2967FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90f074f966bfe2cf45005f01ba35bf5c6bde89c","datavalue":{"value":{"entity-type":"item","numeric-id":3718154,"id":"Q3718154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$FDD80876-4320-4002-9222-B6001EBFF6A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f8aeb1c7725cbf54a781406dbcca5af5bdf571f","datavalue":{"value":{"entity-type":"item","numeric-id":1176317,"id":"Q1176317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$56A44A3D-D517-498F-92C8-CD719B3F6D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23ba82aea6b23a8be0d6632dd9615ef3f7361676","datavalue":{"value":{"entity-type":"item","numeric-id":4696650,"id":"Q4696650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$DCA46688-2757-4AED-B240-DB13451654DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f62acb5eac89db2e3c6032dabab2d88e9279dd27","datavalue":{"value":{"entity-type":"item","numeric-id":4110607,"id":"Q4110607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$CAC5517E-75DB-4B97-A27F-94C6E799852C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89324d361b37a034b5349ba872fc20e8e4a8c32c","datavalue":{"value":{"entity-type":"item","numeric-id":1112724,"id":"Q1112724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$DEB29E99-5908-4709-B811-F9A3E18AACA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"177ca67480d8472fe4cd34339626ecd6ac2177e4","datavalue":{"value":{"entity-type":"item","numeric-id":1176319,"id":"Q1176319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$668F97A7-E7EB-4AF7-A8B1-E1030AE30623","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcdf0f8c0387a6648a8c262f3b165c4b253ed983","datavalue":{"value":{"entity-type":"item","numeric-id":3481743,"id":"Q3481743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$8D0E31EF-8AAC-473C-84F0-48B962D2E358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55670eeffeb14e6ce51166fb8470acff9c12ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5660314,"id":"Q5660314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1312190$57DD5B38-DF29-4690-A6DB-D8F978C4BF78","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"e66fa906d9d7acd8fc9fd3912303128a83f8797d","datavalue":{"value":"journals/dcg/Chazelle93","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1312190$86FCC9E1-9E12-4168-B0DC-2237B3002757","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49b4a7cf9d3b393dff28a8657ae37e8cc58398d9","datavalue":{"value":{"entity-type":"item","numeric-id":1346251,"id":"Q1346251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7951d43992b1f04224bc6bf4c1939a3eaf76823","datavalue":{"value":{"amount":"+0.8706389665603638","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":"Q1312190$8DC45422-03AC-420F-ADEC-610F4A86FD2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cedcda6cf45d4bc0c0291c7552529db5d6a00f84","datavalue":{"value":{"entity-type":"item","numeric-id":1176319,"id":"Q1176319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef83648ac9dc35ca22988de5bf37b42f226eda71","datavalue":{"value":{"amount":"+0.8419065475463867","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":"Q1312190$C8F44B84-AF43-40FD-AC02-5256BD55A001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f18f4a0d2020c446f48ff87d20b6ab32edd83280","datavalue":{"value":{"entity-type":"item","numeric-id":1823685,"id":"Q1823685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a017a906c059647f981f064aece1a6c7d1f5d07","datavalue":{"value":{"amount":"+0.8402152061462402","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":"Q1312190$208EE6C3-51C6-4973-B9BB-51BF3C44771C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b096a530f209e90f7714abaed7fd90d2b1b1d4b","datavalue":{"value":{"entity-type":"item","numeric-id":4016909,"id":"Q4016909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37f65caae3a4e306b506c5f5103c9ef4374ced46","datavalue":{"value":{"amount":"+0.8394604325294495","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":"Q1312190$DAA29DF1-77B7-4E19-9929-BBE0744A0104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a72257f7d91f85d991ae5f7b61db2c9647772708","datavalue":{"value":{"entity-type":"item","numeric-id":1809510,"id":"Q1809510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c39d9a38cf33caa5b38c0834c99be67db385102a","datavalue":{"value":{"amount":"+0.8385133743286133","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":"Q1312190$3FFE2FCB-5450-4232-B297-44107D92D13E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1312190","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1312190"}}}}}