{"entities":{"Q686138":{"pageid":687987,"ns":120,"title":"Item:Q686138","lastrevid":63467619,"modified":"2026-04-11T13:21:31Z","type":"item","id":"Q686138","labels":{"en":{"language":"en","value":"Four results on randomized incremental constructions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 427990"}},"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":"Q686138$EE1715D6-A08E-48C9-8BC0-68BA6C83CA1A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c70dfb88f4ac8c4445c96173c896a91fa05e6795","datavalue":{"value":{"text":"Four results on randomized incremental constructions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686138$24D81F9E-56C1-4944-83E7-262069C44307","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2f32a82f480ce0b24b999328d061dc31b3775cec","datavalue":{"value":"0781.68112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686138$B30777F0-A4CB-4AAE-9772-F1A51CA81ED8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d4aa9f3ffe0ac01b13f2ed6611c815553d0781c4","datavalue":{"value":"10.1016/0925-7721(93)90009-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686138$BAA64BDE-D3BB-4DBF-BFAD-E14B16844654","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a11cffa20d47061797792fb4bbe8768eb9f258ee","datavalue":{"value":{"entity-type":"item","numeric-id":483773,"id":"Q483773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$DF1EC08B-C8E5-46F1-A4B9-A2C84A8DF971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93f2bc7106f436b3e95136cb7027e49039db559e","datavalue":{"value":{"entity-type":"item","numeric-id":270030,"id":"Q270030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$721C22DF-E287-4770-BA81-BA1A213CE623","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b616ea83f16323d1b4f0e42f503e6129370f5d6d","datavalue":{"value":{"entity-type":"item","numeric-id":686136,"id":"Q686136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$35C3D793-DFB5-4F00-B91F-1CC38A6BD9C9","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":"Q686138$4C6A5371-938D-4468-8B6A-03D51E922B81","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"906cc572890000ae504266a724ce23a2bdb9f513","datavalue":{"value":{"time":"+1993-11-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686138$A6CE0DE5-9E41-4262-B74F-E3525436EA52","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0712136ba290f8730fc061c9c77f887578f0c50a","datavalue":{"value":"Some aspects of randomized incremental constructions are studied. Particularly, the expected behavior of the randomized incremental construction under insertions and deletions is analyzed and the results are then applied to the problem of maintaining the convex hull in the \\(d\\)-dimensional space. Moreover a tail estimate for the space complexity (size of the history) of randomized incremental constructions is derived. Also a two-player game related to the randomized incremental constructions is outlined.   In this game one player models the process which generates the insertion sequence, while the other player models the randomized incremental algorithm. Deterministic as well as randomized strategies for the first player are considered, and for both cases a lower bound on the complexity of the game is proved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686138$C6CAB9E5-BF01-4F00-9C0C-08A9FAA249C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686138$BD59B087-7271-483A-9A2C-B123362A6022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686138$C83DF483-9F54-4AF1-82BC-1F8664E55776","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"093cfae0a58c00bbb62018250451d7feaad61745","datavalue":{"value":"427990","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686138$610CC990-6B01-4864-8EE5-28FDA67C5DD8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1773c22e8094ccd95443465df3284fb18604cc41","datavalue":{"value":"expected behavior","type":"string"},"datatype":"string"},"type":"statement","id":"Q686138$33D510CF-E19B-47EB-BD30-C360AADBFA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q686138$EB2BE1B1-64B4-4CFA-88EA-14BC77D7D4AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fc59007b2b1960a263350309435ca1e06e896b5","datavalue":{"value":"space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q686138$1BD09A5D-5605-4381-9D32-74E765F1E21C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6172587e11fd3afaee3932c5b102e77f8e90a75","datavalue":{"value":"randomized incremental algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q686138$B848D329-A997-4FFC-9BDC-D552763C9B6A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$3C8F9D83-78CE-4C99-8237-16F42F2C65AD","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"948b795ec8c8e96daf96f731aa8e8c2afef77d41","datavalue":{"value":{"entity-type":"item","numeric-id":23610,"id":"Q23610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$BE1A7C5D-C504-4AFB-9DFF-9D8E7CE369FC","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":"Q686138$30458375-020D-4F85-BB99-B725A8F89613","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b06effdde7dfe79d99b9664e143d556fb9a2c6c5","datavalue":{"value":{"entity-type":"item","numeric-id":1192610,"id":"Q1192610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$A9F44693-C097-4559-B901-AC7F78073503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59c2ca0e844db29ecd39f75f5228862dbc02c307","datavalue":{"value":{"entity-type":"item","numeric-id":3138981,"id":"Q3138981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$3D21771E-4D94-48B0-8D8B-FB287DE4B349","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":"Q686138$7B7E9A2D-A7F1-4AE7-B661-0A23EFAC5D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b6b67860ca9f66b2db63fdb954fa3ccb4a4302f","datavalue":{"value":{"entity-type":"item","numeric-id":1199828,"id":"Q1199828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$BBBAB360-01E8-437F-9C9D-F552A8DC1707","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":"Q686138$6DD5E13B-538C-4B2B-91A0-60BB769AF203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c61698ae8b8bd6cd61072ff5b5b64e9a52778516","datavalue":{"value":{"entity-type":"item","numeric-id":1185289,"id":"Q1185289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$F9CC6D5B-8E31-484F-BFB4-1BD8BBF50A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9387bbd38b0874a230355988a020913f3259fce1","datavalue":{"value":{"entity-type":"item","numeric-id":3219751,"id":"Q3219751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$864B5284-87ED-477E-BB31-157702EB9584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3791194f6dbf77fef19669add8f2b21e732684c4","datavalue":{"value":{"entity-type":"item","numeric-id":757052,"id":"Q757052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$D54CA1CF-60DB-4A1F-AA49-59434C85F885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b27b8bd426209a0372fd95a59fc40925afbe99a6","datavalue":{"value":{"entity-type":"item","numeric-id":915434,"id":"Q915434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$6BA07C91-9C55-4216-9AA1-A6847D9FCFC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95219ade67c5a2ab70bb1c141c143921a515a3a7","datavalue":{"value":{"entity-type":"item","numeric-id":4023736,"id":"Q4023736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$C0ED3903-AB85-409E-A099-4AC1500BEF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a39eec153bd718a2c45744698baf06a8502d8bf9","datavalue":{"value":{"entity-type":"item","numeric-id":809630,"id":"Q809630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$3AB84751-5E0D-48E1-BB34-5D785A5A3364","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a72d62391449a09ef4c07887febc61402ed34d84","datavalue":{"value":{"entity-type":"item","numeric-id":4137890,"id":"Q4137890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686138$CE4E06CE-0A39-4928-9590-73EFC8FE09D6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7797a675ad0f069ac4b3d5f005401240a7a73629","datavalue":{"value":"https://doi.org/10.1016/0925-7721(93)90009-u","type":"string"},"datatype":"url"},"type":"statement","id":"Q686138$BC1CBC42-19AF-4D91-B40E-FE9FF83285D4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"556cdbaf2e7ace4c07d8bc5907f467f2e5d8ab15","datavalue":{"value":"W2076406769","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686138$96EBEF91-2FFC-4AAA-A6E9-93C6306CEB1A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1dba2b97f0182802e01db44adf97ac18798bbbe","datavalue":{"value":{"entity-type":"item","numeric-id":5096803,"id":"Q5096803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7338aca99d1d9e6f2119888ab4f59f6fb482421e","datavalue":{"value":{"amount":"+0.919723391532898","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":"Q686138$2BD77522-FC3F-4D4C-8963-246D42C43B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72e09cefa5499be278167c2ae8bad6d265910387","datavalue":{"value":{"entity-type":"item","numeric-id":5917712,"id":"Q5917712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"199ddd553604f1cb8e6b34e7c246023a0446e1ef","datavalue":{"value":{"amount":"+0.7900184988975525","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":"Q686138$21DB5A6B-9DE8-4B44-AB52-F0E320198A95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b03f8c8ecfc679dd93ccba755edc0d6b98d2466","datavalue":{"value":{"entity-type":"item","numeric-id":4023736,"id":"Q4023736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16b98c13ae6cfe4dc04f1135c2cd03d26563e560","datavalue":{"value":{"amount":"+0.7879330515861511","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":"Q686138$070AF10E-0FEA-407F-B390-F1886215E5D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82ff8d27997f17862423244499e0f1b6ce43c54a","datavalue":{"value":{"entity-type":"item","numeric-id":1310282,"id":"Q1310282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16b98c13ae6cfe4dc04f1135c2cd03d26563e560","datavalue":{"value":{"amount":"+0.7879330515861511","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":"Q686138$54E2F507-7E71-4E9A-989B-A957D2FF7C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e522702045d5aceafdf9df2f0914bf8f2f3d741","datavalue":{"value":{"entity-type":"item","numeric-id":5896960,"id":"Q5896960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed71c373b6cd0843ca267da4f285bd0cdb4f42e6","datavalue":{"value":{"amount":"+0.7873114943504333","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":"Q686138$6E5F44DA-3AE2-4E33-808B-EEBAE7ED0955","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Four results on randomized incremental constructions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Four_results_on_randomized_incremental_constructions"}}}}}