{"entities":{"Q1093374":{"pageid":1104126,"ns":120,"title":"Item:Q1093374","lastrevid":66117657,"modified":"2026-04-12T07:40:04Z","type":"item","id":"Q1093374","labels":{"en":{"language":"en","value":"The region approach for computing relative neighbourhood graphs in the \\(L_ p\\) metric"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4022653"}},"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":"Q1093374$9EA137A2-328E-4D36-A563-1DD444809D7F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9cbac5c061fee4406b29ce8440ead4f2044fddfc","datavalue":{"value":{"text":"The region approach for computing relative neighbourhood graphs in the \\(L_ p\\) metric","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1093374$B9E666D8-7F23-4775-AE5B-1679F912C225","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"357451ac9ac5ce3bb0ffecbb82222ed21ff6e1f8","datavalue":{"value":"0628.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1093374$A779899E-69A9-45F9-8DC8-D729068DD66E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"132f43a1f3ada855b4751f0e16fc79547bf8bce2","datavalue":{"value":"10.1007/BF02247943","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1093374$1DC00088-782F-47E8-AB14-15299BAA3BD6","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":"Q1093374$5F00CA0D-AE4E-4AFD-AE4A-53937E71A274","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$6B2D1993-43DC-4639-8EB3-249BF493E431","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1093374$CF11CE1A-D8F8-4ECC-B89F-B6AF7BE0C7C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1dea6f12be4a577d52151f6c1156dceef9f88a59","datavalue":{"value":"The following geometrical proximity concepts are discussed: relative closeness and geographic closeness. Consider a set \\(V=\\{v_ 1,v_ 2,...,v_ n\\}\\) of distinct points in a two-dimensional space. The point \\(v_ j\\) is said to be a relative neighbour of \\(v_ i\\) if  \\[  d_ p(v_ i,v_ j)\\leq \\max \\{d_ p(v_ i,v_ k),d_ p(v_ j,v_ k)\\}\\quad for\\quad all\\quad v_ k\\in V,  \\]  where \\(d_ p\\) denotes the distance in the \\(L_ p\\) metric, \\(1\\leq p\\leq \\infty\\). After dividing the space around the point \\(v_ i\\) into eight sectors (regions) of equal size, a closest point to \\(v_ i\\) in some region is called an octant (region, or geographic) neighbour of \\(v_ i\\). For any \\(L_ p\\) metric, a relative neighbour of \\(v_ i\\) is always an octant neighbour in some region at \\(v_ i\\). This gives a direct method for computing all relative neighbours, i.e. for establishing the relative neighbourhood graph of V. For every point \\(v_ i\\) of V, first search for the octant neighbours of \\(v_ i\\) in each region, and then for each octant neighbor \\(v_ j\\) found ckeck whether the point \\(v_ j\\) is also relative neighbour of \\(v_ i\\). In the \\(L_ p\\) metric, \\(1<p<\\infty\\), the total number of octant neighbours is shown to be \\(\\theta\\) (n) for any set of n points; hence, even a straightforward implementation of the above method runs in \\(\\theta (n^ 2)\\) time. In the \\(L_ 1\\) and \\(L_{\\infty}\\) metrics the method can be refined to a \\(\\theta\\) (n log n\\(+m)\\) algorithm, where m is the number of relative neighbours in the output, n-1\\(\\leq m\\leq n(n-1)\\). The \\(L_ 1\\) \\((L_{\\infty})\\) algorithm is optimal within a constant factor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093374$15BF2D01-E8F3-4B5D-B65F-4D96A78C3272","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1093374$2C478134-1E9A-433B-9BEA-6CA2ED41BCAF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7f0f12f31e5632681615ca6b3804eee95e9fa8e0","datavalue":{"value":"4022653","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1093374$3A9C6FD0-1375-48E0-AF64-9B6DAB8FC355","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7729d1d61a23d8ce1be3ed2e11decab6a351e905","datavalue":{"value":"region approach","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093374$19C095BA-2D80-4153-B395-F1BD939AC3C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e572043101b55832535239368b70365e1e6ce123","datavalue":{"value":"relative neighbourhood graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093374$47144ECE-379C-43D6-AB56-BA214672D589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e13226896772781f16a7d6061185ca399b94694e","datavalue":{"value":"range searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093374$9D1F7499-2866-4100-BEEE-F869774590F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093374$BDA58495-11D8-40CF-8A1D-1BABCA5541BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093374$D82715C4-7A58-42B7-94AA-38AD15AE0986","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":"Q1093374$7DCA4A9F-E8E2-46E6-94DC-03F2DA165BF6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8473e563ea89198d269dd9b56789cfdbada12f16","datavalue":{"value":{"entity-type":"item","numeric-id":1134522,"id":"Q1134522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$DD39A9EA-C7C1-4AAA-B4E7-573A19023B48","rank":"normal"},{"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":"Q1093374$72B52EA9-57E9-4557-A9D1-9924A7F24282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd2eefc175d55ef5b4fe824717af8023e20e88fa","datavalue":{"value":{"entity-type":"item","numeric-id":3753527,"id":"Q3753527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$E1117C6A-9FBE-4FB9-B793-0B7CDD6419E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c662ce83fa2c4126f1c1de81b70991549cde3a07","datavalue":{"value":{"entity-type":"item","numeric-id":3859256,"id":"Q3859256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$4F6F9229-D55F-4E54-BC2F-35F3EF4AFBD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d78a9507c90effc4cde0f3d761d267db382be1b5","datavalue":{"value":{"entity-type":"item","numeric-id":3707419,"id":"Q3707419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$C4DC84A3-92CF-47B1-A12E-C4C8404891CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4249e9f2a695f80f99df1b937c95ab5000716da8","datavalue":{"value":{"entity-type":"item","numeric-id":1055197,"id":"Q1055197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$71D1DF91-7A85-4C6C-BD6B-81D85F3EAB53","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":"Q1093374$504E08EB-3A8A-4C6D-98E2-238E48727AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40de7b6af58345cf79cf8cde21531a4d23cba659","datavalue":{"value":{"entity-type":"item","numeric-id":3773333,"id":"Q3773333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$8ED3A60D-D70B-4EA4-955A-C95A4EFEA3F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"802f3d9b7097035d4031148bd30e4cb1d1f0af14","datavalue":{"value":{"entity-type":"item","numeric-id":1108002,"id":"Q1108002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$2EF753B4-0237-4B36-8F76-3CCD27499BB2","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":"Q1093374$3B6B9AF8-B8A2-490B-826C-09F02F06CB2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8abbc586764dd416af48f9699aa05c8e6f910dbe","datavalue":{"value":{"entity-type":"item","numeric-id":1165014,"id":"Q1165014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$04985FDC-BA1A-4379-A8B3-965B78F4B221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd1462286ac5df294dbd58d9be71779e0279c3c","datavalue":{"value":{"entity-type":"item","numeric-id":797269,"id":"Q797269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$D90CCFE7-7D78-4B5E-82E9-E9EF4255A099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08bbfa2750c080ec67d6b7bc35b58e0a9bc36c96","datavalue":{"value":{"entity-type":"item","numeric-id":3694703,"id":"Q3694703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$62023F91-7ECF-4766-BC50-DFDC1C84E8F1","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":"Q1093374$B234D22D-F709-4700-8169-5199C8F78D8E","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":"Q1093374$E33B769C-24EA-49C6-84E1-34D9B6166408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfc315b1465b84130dbf7cf5abc6d0917ad160d7","datavalue":{"value":{"entity-type":"item","numeric-id":3920971,"id":"Q3920971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$E0D49900-FB2B-4142-A19C-6CA14D80AA39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d672eac138c6d0bcbb771f4bd791fdd309356f14","datavalue":{"value":{"entity-type":"item","numeric-id":3660948,"id":"Q3660948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$03CEFFE1-BDC0-4DCE-A3FB-2D43421A9A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db8343e526f156f1469a28b5688ff6513e9b7246","datavalue":{"value":{"entity-type":"item","numeric-id":3678701,"id":"Q3678701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$ACAA3486-24F3-4778-8C4E-B1D15549E136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a49d6af7b2df96ccb57b811f981edcbee6fa50fc","datavalue":{"value":{"entity-type":"item","numeric-id":3954830,"id":"Q3954830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093374$BB1F7184-7875-4F9D-B738-5917A829FC75","rank":"normal"}],"P1643":[{"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":"fee63ca11a6869077f5435d68189c2587ae9cd48","datavalue":{"value":{"amount":"+0.892386794090271","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":"Q1093374$91217BE8-88BD-4AA8-B027-5047EF1BCB9E","rank":"normal"},{"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":"f540c92a52086b03bd7cbbcee1530486b83c7497","datavalue":{"value":{"amount":"+0.8066184520721436","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":"Q1093374$2C74479C-9B69-47D8-9E90-384A1808406E","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":"8f68dfba63875fe9f21e8137428428a18f8cad06","datavalue":{"value":{"amount":"+0.8037744760513306","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":"Q1093374$720A9017-4EF8-4875-B0EF-FF8590A56E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34f4025ad6fc4abf4196c18b35be7fd1e2760077","datavalue":{"value":{"entity-type":"item","numeric-id":4557732,"id":"Q4557732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44170fe797857a10665d94e264ef2acac154b87b","datavalue":{"value":{"amount":"+0.7807655930519104","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":"Q1093374$F2AB55EA-64FE-48D1-AEDB-515B1DEE00C0","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":"c1d3fe5a5aca6a763ba880b6884ef8895c0bfc75","datavalue":{"value":{"amount":"+0.7780711054801941","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":"Q1093374$478A3319-7709-40EE-80B5-7D2FFC56A187","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The region approach for computing relative neighbourhood graphs in the \\(L p\\) metric","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_region_approach_for_computing_relative_neighbourhood_graphs_in_the_%5C(L_p%5C)_metric"}}}}}