{"entities":{"Q1094872":{"pageid":1105624,"ns":120,"title":"Item:Q1094872","lastrevid":66712086,"modified":"2026-04-12T12:19:20Z","type":"item","id":"Q1094872","labels":{"en":{"language":"en","value":"A faster divide-and-conquer algorithm for constructing Delaunay triangulations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4026829"}},"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":"Q1094872$BB229AF9-FED2-4E4F-94AE-147DD728F7B8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"39e03e834f65ca438f8183807e9e7f46f5826aa3","datavalue":{"value":{"text":"A faster divide-and-conquer algorithm for constructing Delaunay triangulations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1094872$14F2785B-5E6F-4606-9B72-4116E39F03AE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae7ff06a8fbe8bb1bd3bbca8d124327b8978e412","datavalue":{"value":"0631.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094872$85545472-736F-4D5A-9139-033B3138171E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f722a8010f4a291372cac9382c2e8e720d5e73e7","datavalue":{"value":"10.1007/BF01840356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094872$82E14A89-BCBE-4CC5-979B-449BC7BD097B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c0ac5cadcc44a60885f190b2c59f06d52be57f08","datavalue":{"value":{"entity-type":"item","numeric-id":804319,"id":"Q804319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$083B7FC6-8E8A-4C6C-AABB-C71F4038A9FC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$39D7D691-5FC6-4B19-A1AD-62F2EF6A4F06","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1094872$2D3CD2FD-B392-4A39-B5FE-A182CA858A49","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d4edf68bda12876cd5295513ee116e8b703e83a0","datavalue":{"value":"An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation of n sites in the plane is presented. The change reduces its \\(\\theta\\) (n log n) expected running time to O(n log log n) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well for \\(n\\leq 2^{16}\\), the range of the experiments. It is conjectured that the average number of edges it creates - a good measure of its efficiency - is no more than twice optimal for n less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in the \\(L_ p\\) metric for \\(1<p\\leq \\infty\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094872$C2B2BACD-73D2-4F00-B978-20F930AB4BB8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094872$41EEDF95-B65F-41F9-9DF5-DB3A7D0B7253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5ae9e2988e76d371f7e87b79bcd004ea2b80f64","datavalue":{"value":"51M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094872$B0AADA8F-BDA2-480C-80AF-BDDFF7C9B9FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"671a9141f7533e3d7d525a297ffd04f047259a12","datavalue":{"value":"60D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094872$7EB8049A-59EB-415C-A27E-802235B0DEE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094872$D2C43AF1-6DDF-42FB-A066-B170269EB06A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ffea8235005727be25a990def37da6e2a8fe4d3c","datavalue":{"value":"4026829","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094872$68B22DE3-55A8-4ED8-868C-86A797867BAC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d975c8e13006fbe9b4f6c347ea88f3b06e6e4c7","datavalue":{"value":"Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094872$876F0647-17D2-42C0-A031-CA1B27635D09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094872$7F5687B4-7FD6-40E3-9CFE-680761097591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeb5cf5222b6371fb7f9c168c78eb205663c9be7","datavalue":{"value":"average-case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094872$5CCB6DCE-2EEA-4637-990D-F5555BAC4372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094872$66BBBC2C-DBDC-4B89-815B-73372C507FA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5edfd6368999620c7e10cbba2e058c2b660abfd0","datavalue":{"value":"Delaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094872$AC130728-1DAA-4022-A6BB-6E9F871FBC9A","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":"Q1094872$09D70795-163A-47BE-AB49-8F19469E34D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b11f46880b422209c9517febd241f5ae6afb3de","datavalue":{"value":{"entity-type":"item","numeric-id":3883531,"id":"Q3883531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$8D0C632F-AF7B-4559-8AC0-0CBD2BB28D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff4e812fbcc008a1d5259e712cd9203d973f596","datavalue":{"value":{"entity-type":"item","numeric-id":3711764,"id":"Q3711764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$6EB5C327-C387-4945-B16E-958B8CBB56D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29d0699d9da26d4080770c380efdeb17f5d5ec21","datavalue":{"value":{"entity-type":"item","numeric-id":4178506,"id":"Q4178506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$C83E3F06-0588-45BA-8F74-463EB5D03234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9489fe87a33a78d7ec9f473c64ac69f198384f52","datavalue":{"value":{"entity-type":"item","numeric-id":4194442,"id":"Q4194442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$29A9C624-BEE5-43D0-BF2C-821D46196A57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2f422a6126daf14d9bc38a3327ee84be4512e26","datavalue":{"value":{"entity-type":"item","numeric-id":3890127,"id":"Q3890127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$F29B7AC3-4879-4C7F-8D3B-5ACF440C1B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"794e24faea6d10ca38a88bb803e4681f9768e955","datavalue":{"value":{"entity-type":"item","numeric-id":3883495,"id":"Q3883495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$E41647B3-D2AE-495F-9891-BB12CC285E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58d427a7be7364e105f0eb9a2691d3825b86ff8f","datavalue":{"value":{"entity-type":"item","numeric-id":3893362,"id":"Q3893362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$E336BDFA-2ED2-48E9-B785-8CF4D17DC6D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2bb0571cd57e52e3bd40f60cf30dbfd97b3d170","datavalue":{"value":{"entity-type":"item","numeric-id":4082929,"id":"Q4082929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$277B4EE5-EB89-426B-ADE9-59E71CCE1C0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07265a1e36253f3446e2d6661c182bfed2a0f5a0","datavalue":{"value":{"entity-type":"item","numeric-id":799379,"id":"Q799379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$3B5F24E4-0A9F-413F-8A5D-B2A23A4B1627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"180a6a9d9b838ff499f381b95e9c7ba7495e9808","datavalue":{"value":{"entity-type":"item","numeric-id":3219793,"id":"Q3219793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$49EBEDBC-857A-478B-965C-FD70B8ECDDBA","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":"Q1094872$2780EF12-90E3-4083-9F44-4E5F62FF68A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe687805020d5fa4748df861743399851d2b4d00","datavalue":{"value":{"entity-type":"item","numeric-id":4157261,"id":"Q4157261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094872$87359945-4191-4D92-ABF6-B8188D5CEC93","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7ffa01faaf2a20ef8da72dd077d2610daf1b7f36","datavalue":{"value":"https://doi.org/10.1007/bf01840356","type":"string"},"datatype":"url"},"type":"statement","id":"Q1094872$1197142B-08C5-4D7D-8BC0-43A27E02314A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3979b27d251329b2b870f8e94a0523215da8903d","datavalue":{"value":"W1991064236","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094872$4BCD06F0-C5B6-400C-B0F6-7DA36059F099","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c0adc396d0ef1d8997936764ee24f273eefe3bc","datavalue":{"value":{"entity-type":"item","numeric-id":3765247,"id":"Q3765247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"247a297924f863f71cca36b0a3e672fa219cfc01","datavalue":{"value":{"amount":"+0.8756887316703796","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":"Q1094872$BF5324B6-72AD-40B7-A288-AF7421445242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ffeeee10506f45b72a9ff5e27582ba573101a0b","datavalue":{"value":{"entity-type":"item","numeric-id":3796756,"id":"Q3796756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21d9d7a7845fa7177d7f2ae0aaefed64f3adc6bb","datavalue":{"value":{"amount":"+0.869084358215332","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":"Q1094872$C8C0C58A-B558-450E-97C3-7D7F67E2002F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a4731d7e889db38fd7980c763cbf9639de7d9d7","datavalue":{"value":{"entity-type":"item","numeric-id":799379,"id":"Q799379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0315a7eeba9241b153ae32532b8e7b0aa152dd0","datavalue":{"value":{"amount":"+0.8675850033760071","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":"Q1094872$25265673-6BE5-4E7B-A686-A7B06F469964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69c6ac8db83850e067baadeae51133115a832938","datavalue":{"value":{"entity-type":"item","numeric-id":2482895,"id":"Q2482895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb99ce66e2b529922267e7f75a1636764a7d26d1","datavalue":{"value":{"amount":"+0.8555023670196533","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":"Q1094872$F28F2CD4-3D05-43CB-885F-111E6118719F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"845bfecc8964c1b3974723f4db1450d66ca7e9d7","datavalue":{"value":{"entity-type":"item","numeric-id":1841245,"id":"Q1841245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83c99edf3fc97925d354e150d309c0fddcd1128d","datavalue":{"value":{"amount":"+0.8525061011314392","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":"Q1094872$84B0BD76-7FDF-4308-8E2D-7DF01C1545C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A faster divide-and-conquer algorithm for constructing Delaunay triangulations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_faster_divide-and-conquer_algorithm_for_constructing_Delaunay_triangulations"}}}}}