{"entities":{"Q799379":{"pageid":801227,"ns":120,"title":"Item:Q799379","lastrevid":64501551,"modified":"2026-04-11T20:18:23Z","type":"item","id":"Q799379","labels":{"en":{"language":"en","value":"Delaunay triangulation and the convex hull of n points in expected linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3874637"}},"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":"Q799379$317B3F81-A62B-4053-8D62-2732FBDB4743","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"953c16dfdb3149302ddd9843390c9b4d92bfa30a","datavalue":{"value":{"text":"Delaunay triangulation and the convex hull of n points in expected linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q799379$D601EA92-BE74-4827-9D1B-B09795101835","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e9e02e4675cdc4b13c55f4e9ee0fcf8f97bc3df7","datavalue":{"value":"0548.68068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799379$465C69E5-4940-47EF-B777-425E4258AC80","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2f28b8862f032da0a616b7900f549ce7574249fe","datavalue":{"value":"10.1007/BF01937482","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799379$D213B60A-2118-4B9F-852E-C37FBF4FBFF6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5d915cd726844d7a1a35d5587737f942bf6ba7d6","datavalue":{"value":{"entity-type":"item","numeric-id":799378,"id":"Q799378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799379$1D87326B-25C8-4D8F-97AB-7106788D0B87","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799379$6E111DB2-C2D4-4F97-8898-8AB0859B613D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q799379$5A90CB32-3D71-42CC-B2F7-4E5B60B50601","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f68caa88fcbc7b65d91e87b469a71b6cfbbc5d7a","datavalue":{"value":"An algorithm is presented which produces a Delaunay triangulation of n points in the Euclidean plane in expected linear time. The expected execution time is achieved when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix treats most of the non-uniform distributions. The basis of this algorithm is a geographical partitioning of the plane into boxes by the well-known Radix-sort algorithm. This partitioning is also used as a basis for a linear time algorithm for finding the convex hull of n points in the Euclidean plane.","type":"string"},"datatype":"string"},"type":"statement","id":"Q799379$CD922317-3ED9-41B4-87B1-F812F8B83766","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799379$34FBA775-A0AB-4931-8E37-6F11BB7097A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799379$60FDD4C4-C87C-4F1C-BC4C-CD4EEB7A59E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799379$D8C84063-20FF-4621-A793-4C02BBFC6861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799379$8342CE74-562E-48F2-BCF8-73349CCB1BFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58d33fcd5e5cb8a52812aa5e4a2f3f30b5cf0e30","datavalue":{"value":"05A17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799379$5B076527-AF97-454A-98CC-3BDA6CC97CA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5ae9e2988e76d371f7e87b79bcd004ea2b80f64","datavalue":{"value":"51M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799379$5126D8BD-363C-4891-B066-1C9A58E60F33","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71645241da2e16c681d00d35c1a402a503fab433","datavalue":{"value":"3874637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799379$61A6721A-4C20-4784-A24C-4A6C478544FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8639e8ff38e314b6cb0837d4589290560176ad4e","datavalue":{"value":"Voronoi polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q799379$DFEF4292-4955-44AE-931C-A020086C2682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5edfd6368999620c7e10cbba2e058c2b660abfd0","datavalue":{"value":"Delaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q799379$41608FCE-519B-4A57-9D74-BDB27B010A2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4be943fe9965f649689587a65f0153f5a1f630c0","datavalue":{"value":"Radix-sort algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q799379$1B019105-04ED-4189-B095-328D048C6FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q799379$8C384152-5289-433A-BA98-9E6BDC137C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q799379$C32497B6-7CD4-464A-A7FE-B9B6DCAADDFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4db5494d3f7b8f844dd8114683f2cc3cdcc9e9d8","datavalue":{"value":"Euclidean plane","type":"string"},"datatype":"string"},"type":"statement","id":"Q799379$D25A1831-C12A-4CDC-BEC0-CA298DC44B89","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":"Q799379$A29FD7AD-EB3F-4599-8B95-54753F58B579","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799379$559EF8E5-6BB1-4E10-A5FA-D5C38ACFDAC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca70d8e4f894483b4a8a4c045a224418a869f655","datavalue":{"value":{"entity-type":"item","numeric-id":1162818,"id":"Q1162818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799379$083CA8C6-C8C6-4927-B7D6-F7DEF0771AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"650443d9ef00d57d2be1129773112271216a2b40","datavalue":{"value":{"entity-type":"item","numeric-id":4760292,"id":"Q4760292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799379$2C6845D8-F938-4EEF-A8C5-2890644367BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f545c2db529ae3050e745aa3193c438be89c47fc","datavalue":{"value":{"entity-type":"item","numeric-id":4151725,"id":"Q4151725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799379$094B8F5C-B1B4-438C-80AA-0D877435BC78","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":"Q799379$34A8CE16-AFD2-4AA9-8C7B-E9C230C714F3","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":"Q799379$8BA0953B-D314-4D6A-8C8B-30629B52DF0B","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":"Q799379$6E765D44-9215-4246-A2EC-722011E380ED","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":"Q799379$B89AC05F-85C7-41DF-AC01-64D750646C15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55f9b2ed5ac208b7e8872aa85639f7fa2237f8cf","datavalue":{"value":{"entity-type":"item","numeric-id":3875133,"id":"Q3875133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799379$D82ABF90-48E0-48A7-B2BD-E187394F5B8F","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":"0ebd4a5718e0b513583c2e44f81229ffc7c952b6","datavalue":{"value":{"amount":"+0.8699853420257568","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":"Q799379$05DBC254-8B90-4E3A-B958-3C716E271CD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c805dae4f18e77f32565a8610fc646997e18663","datavalue":{"value":{"entity-type":"item","numeric-id":1094872,"id":"Q1094872"},"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":"Q799379$8F009B0B-DCD6-4D13-A1C8-6AE052B5FA77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c5c344a5fbfd546aec7f8202220e10cf076af85","datavalue":{"value":{"entity-type":"item","numeric-id":4796184,"id":"Q4796184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea37a317019db65981b8a9f1e2245c1425eced6a","datavalue":{"value":{"amount":"+0.8500831723213196","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":"Q799379$750A3244-3084-468B-A891-53F736F81C63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db0be53d6695b46d48c08e24ff415dcd8e1d22b7","datavalue":{"value":{"entity-type":"item","numeric-id":807005,"id":"Q807005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea37a317019db65981b8a9f1e2245c1425eced6a","datavalue":{"value":{"amount":"+0.8500831723213196","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":"Q799379$CE6962C1-172B-4212-AA5E-1E1EDC235581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d907315b46d6db8936fbeb17b5313f36895c54d","datavalue":{"value":{"entity-type":"item","numeric-id":3974960,"id":"Q3974960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec2a031b4bfb7298e6c9bcb585fb28d0b6c730fc","datavalue":{"value":{"amount":"+0.8472216725349426","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":"Q799379$276FFE8F-786E-4653-AAF3-E8FD90A87FB3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Delaunay triangulation and the convex hull of n points in expected linear time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Delaunay_triangulation_and_the_convex_hull_of_n_points_in_expected_linear_time"}}}}}