{"entities":{"Q1108002":{"pageid":1118751,"ns":120,"title":"Item:Q1108002","lastrevid":49201141,"modified":"2026-01-06T18:24:26Z","type":"item","id":"Q1108002","labels":{"en":{"language":"en","value":"A linear expected-time algorithm for computing planar relative neighbourhood graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4066328"}},"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":"Q1108002$94A1B4F7-6757-45BD-8FC3-2B5BDC1AD9F5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c7b05883de763ac3a251cd1e0c944b3589eb5c48","datavalue":{"value":{"text":"A linear expected-time algorithm for computing planar relative neighbourhood graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108002$141B24A8-AFC4-469F-A215-2D96F1B97C94","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3151fbb3af8a67d16520396c7bed0d714b971ba9","datavalue":{"value":"0653.68034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108002$09B8CD6B-5D61-41D6-9B2B-A7D1CE10C660","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"93741548e203fa93fe17a53413bd82c15fb81bb2","datavalue":{"value":"10.1016/0020-0190(87)90225-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108002$44E19C50-C7B1-4BF1-9249-937E09479570","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2fe70195d1e0d46d568646f1bb894a0f78708017","datavalue":{"value":{"entity-type":"item","numeric-id":396691,"id":"Q396691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108002$CB4A13B0-6E57-4703-87C4-24C84FB6BDA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0325abe64279e840e08f553b87295670b19a2b45","datavalue":{"value":{"entity-type":"item","numeric-id":1108001,"id":"Q1108001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108002$AB418682-5AF1-415C-9441-B58E23B0E850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e31cbbff520e6b5595a561efbb871b80716714a","datavalue":{"value":{"entity-type":"item","numeric-id":336589,"id":"Q336589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108002$D72EB94E-89B1-4F82-9E75-476157976061","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108002$2132B6D9-87E8-4BA9-B7A5-6E6A14E384BE","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":"Q1108002$31CBF99E-23D9-4546-A5F4-EC672B99061E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d5adc7020b8b1311a614904cd2ec6cec5329f7b1","datavalue":{"value":"A new algorithm for computing the relative neighbourhood graph (RNG) of a planar point set is given. The expected running time of the algorithm is linear for a point set in a unit square when the points have been generated by a homogeneous planar Poisson point process. The worst-case running time is quadratic on the number of the points. The algorithm proceeds in two steps. First, a supergraph of the RNG is constructed with the aid of a cell organization of the points. Here, a point is connected by an edge to some of its nearest neighbours in eight regions around the point. The nearest region neighbours are chosen in a special way to minimize the costs. Second, extra edges are pruned from the graph by a simple scan.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108002$152025B1-4D8E-469F-BD81-41783E2B1ED7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108002$595030EB-3B1C-4FCA-94F2-DB4E57BCDC59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108002$FFD6EEFB-FA74-414E-B0D1-2EF3254E7B93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108002$E29F8BCD-2F52-4BE2-A964-B353F55BBC4B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"46bb2de0ad44d31c255a2b92be723052fe709d8d","datavalue":{"value":"4066328","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108002$3C22819F-6822-4140-9EE8-C0EF1C43D9AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d975c8e13006fbe9b4f6c347ea88f3b06e6e4c7","datavalue":{"value":"Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108002$AFAF6527-EAF4-4EC4-B2B2-BF41333D01A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9938c8186ebfc71c6a612001fa7b768a472c07e4","datavalue":{"value":"cell technique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108002$AEE8EDB1-467E-4649-A82F-E0DDACF751BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7729d1d61a23d8ce1be3ed2e11decab6a351e905","datavalue":{"value":"region approach","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108002$D0CAF2D8-3083-47BB-AD70-47F6A6FE88B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108002$4C906351-7ED7-4D65-AB19-2142434B1C9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6d44e406c6b3806280e22b06e54abe9955407bd","datavalue":{"value":"relative neighbourhood graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108002$5AC51FDE-0D86-4DD6-8ED0-1EFF31350A22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca96a92e60254ac0bcbfa37f857aa0f79017cf8d","datavalue":{"value":"planar point set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108002$28388E10-1A41-4284-A017-843E52C9F42E","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":"Q1108002$B07F5049-6116-4E5C-AB24-374A00D32F88","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3ac37370488bf9f17a0d4729700581a0b3918771","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90225-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108002$EAB84300-2274-4910-934C-A3F0E14FD01F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d5532b4456bc517170175669d3e65502d89e2185","datavalue":{"value":"W1993153243","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108002$4A8CE4D6-5FA5-4838-A2BB-4BFE7B641087","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":"Q1108002$19DC3BED-206D-461F-B155-807AB875AA61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3672b77003aec8354249ed95a96935240d1d7d11","datavalue":{"value":{"entity-type":"item","numeric-id":1093374,"id":"Q1093374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108002$A40A174C-6CC0-4230-B5E7-DD707074856D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c11edfe5ebb1d08834877df8ac4f32f45ee7cc1a","datavalue":{"value":{"entity-type":"item","numeric-id":1082094,"id":"Q1082094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108002$81427241-E661-401F-A6AC-FA09CC027E38","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":"Q1108002$EEA5EFC8-342A-4256-8B55-DCFCAD21C933","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebbdee902de4af6b50be280c18f6a011e48d4b17","datavalue":{"value":{"entity-type":"item","numeric-id":4125549,"id":"Q4125549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108002$3DC18DBF-B11E-4DCE-B08E-ACBDFA38E0C4","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":"Q1108002$99F1DED8-5448-4FBA-81E7-CEB1F68DDC5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c49b07ca7b15dac046e5e43f04c1843935ce6abc","datavalue":{"value":{"entity-type":"item","numeric-id":3028354,"id":"Q3028354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108002$4E783E17-9B9E-4E49-AC6A-8ED6F0EFA776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"016484174b8f6c44c2f7655ecac9124cf75bba8d","datavalue":{"value":{"entity-type":"item","numeric-id":1141155,"id":"Q1141155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108002$98E6D049-232E-4FD6-A89D-CF574D8B59BF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"803779ec658b9f757c6b15b4774ea443e136dad0","datavalue":{"value":{"entity-type":"item","numeric-id":1082094,"id":"Q1082094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6047024710e3eb20683ca81cc20b13ba6b413acf","datavalue":{"value":{"amount":"+0.8945760726928711","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":"Q1108002$F219A0B2-5D93-49B3-AEF2-99D8AB4684B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"617cc93d6dd0833a339bc4d1df82461045e05f2f","datavalue":{"value":{"entity-type":"item","numeric-id":3773333,"id":"Q3773333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33180197f8b7ab2f83297471c388d00f3bf9b62b","datavalue":{"value":{"amount":"+0.8686970472335815","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":"Q1108002$23AF191A-E12D-4090-AC33-56560B97685E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"beedb1e4b435b3383b3436078d93f6b48bdac807","datavalue":{"value":{"entity-type":"item","numeric-id":3028354,"id":"Q3028354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7648a5e879f7c354ef9f53e5677ed14609ca473","datavalue":{"value":{"amount":"+0.8599998950958252","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":"Q1108002$71A94F6B-D771-4950-AD73-2D4B88244699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bf9693ea7a0af674ca60998052f5ce9fd412418","datavalue":{"value":{"entity-type":"item","numeric-id":1200909,"id":"Q1200909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be24cea599a7f24e7a9fcb8ae06e13c1521ce873","datavalue":{"value":{"amount":"+0.8545246720314026","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":"Q1108002$EAA34237-72E0-4065-B011-BE84FAB6F069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df527e505bbb315e99eb3b52a7a96c3e29ceacdf","datavalue":{"value":{"entity-type":"item","numeric-id":1334610,"id":"Q1334610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20a3fafc68e16278c1828fe8a6246fb26e997c65","datavalue":{"value":{"amount":"+0.8538663387298584","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":"Q1108002$39CA0CCE-CAEE-4EE9-82E8-626212EFB758","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1108002","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1108002"}}}}}