{"entities":{"Q1071508":{"pageid":1082260,"ns":120,"title":"Item:Q1071508","lastrevid":69787962,"modified":"2026-04-13T09:23:35Z","type":"item","id":"Q1071508","labels":{"en":{"language":"en","value":"The one-dimensional weighted Voronoi diagram"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3940721"}},"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":"Q1071508$43E4E7C9-74F0-4561-850C-4E143351CD02","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a688833266a782eb8fe51d08d8af2558f15de5a","datavalue":{"value":{"text":"The one-dimensional weighted Voronoi diagram","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1071508$5AD7C9A0-6CCB-45D3-A41D-FE327EE77049","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"87faa92e716d032de9905c8d1ed0abd3510bb3fd","datavalue":{"value":"0586.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071508$EF866549-DE57-4E7B-9A6D-36DF8F424DAC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6ae7dffdeb1a7085d781ca32b6139327a767469","datavalue":{"value":"10.1016/0020-0190(86)90055-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071508$4441CDCF-F2C6-465A-ABDA-722B90BD9411","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"69dce50474062592c3f0f665321210ea0d53ae77","datavalue":{"value":{"entity-type":"item","numeric-id":170469,"id":"Q170469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071508$BBD40DBD-3BE4-430F-BC0E-8776A23AAED8","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":"Q1071508$6304DBED-A9E4-4392-A8E8-274F822DCC5A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1071508$741CDDEE-270E-4AC1-B23C-F55B301C9BC5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f959d3e57b44eb90a8efbf23d8403021b83f6fc2","datavalue":{"value":"Let \\(S=\\{p_ 1,...,p_ n\\}\\) denote a finite set of points on the x- axis, and let each \\(p_ i\\in S\\) have an associated weight \\(w(p_ i)>0\\). The weighted Voronoi diagram WVD(S) of S is a partition of the x-axis into regions  \\[  reg(p_ i)=\\{x| \\quad | x-p_ i| /w(p_ i)\\leq | x-p_ j| /w(p_ j),\\quad p_ j\\in S\\},  \\]  for \\(i=1,...,n\\). Although \\(reg(p_ i)\\) may consist of O(n) disjoint intervals, the total number of intervals realized by WVD(S) can be shown to be bounded by 2n-1. Furthermore, WVD(S) can be constructed by a simple divide-and-conquer algorithm in optimal time O(n log n) and space O(n). Both results heavily rely on a two-dimensional interpretation of WVD(S) where, intuitively speaking, the weighted distance \\(| x-p_ i| /w(p_ i)\\) from \\(p_ i\\) is considered as some kind of speed an interval around \\(p_ i\\) expands with. The geometrical concept of WVD(S) and its analogues in dimensions two and three have applications in geography, economy, and biology.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071508$21096360-2CDC-4A63-8029-004BE0ABF20F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071508$0563F021-CE60-4738-B914-53378C5BBC0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071508$BFB35622-777A-4CEB-A223-48391DC2AE8F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bbeecc1a7ac6e0447cc09321d8e0a0b3d8d64d14","datavalue":{"value":"3940721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071508$33933B42-7E06-4B86-B56E-C95819026CD1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071508$2FBAB12C-532B-4B7E-9455-FD4FDA11EF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88ddb8b7cd619a2db597ce5172c75384264dad0f","datavalue":{"value":"geometric interpretation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071508$3F489771-6D4D-4CFC-8B91-2310BDCCFC1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc00012563a75ed0c7975e9c32d5f2d16f0982e3","datavalue":{"value":"optimal algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071508$99351B7F-F8D4-44E7-83AB-63F6CBC46341","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":"Q1071508$566666D4-D00D-46F4-BA4A-4E1E21E835B9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"35d07753269939855fb6f3777acecb2865ff4c64","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90055-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1071508$4FC38BFF-CB8F-4D0B-858F-1421427D6A76","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"27291c023d9e59669a7def5d21d10a0c81ad991f","datavalue":{"value":"W2005915375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071508$8EA9712C-1F58-4665-A199-DC5271D218AC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071508$A7F976E5-2EC8-4DDA-823B-D9F0F2271E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e9e1629289c17adbbe0b8b3786cfc15c2541b48","datavalue":{"value":{"entity-type":"item","numeric-id":4725255,"id":"Q4725255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071508$3B045811-455C-46F1-83AD-286A0C143633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1a25a12f37c3deaa3b693b3039e8ee635595916","datavalue":{"value":{"entity-type":"item","numeric-id":793982,"id":"Q793982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071508$A1BDE29B-3E99-4F41-9C37-F5D16AC258F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d87a027c696d4cca9cf462e499936419e44e67","datavalue":{"value":{"entity-type":"item","numeric-id":1163869,"id":"Q1163869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071508$6BFA0E61-F0FD-4686-9654-6BFFEB842B66","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":"Q1071508$B074079F-B797-4E99-93DE-D7BA3DF773EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d6997999afb1d8c9592b71e9e8c4b4eb7f4ea7a","datavalue":{"value":{"entity-type":"item","numeric-id":3902522,"id":"Q3902522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071508$9B9A85C2-F209-4618-82E6-9E03CC46D43D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a424f44a8dbc665539390a6f9c8785edbdbed5f3","datavalue":{"value":{"entity-type":"item","numeric-id":3953198,"id":"Q3953198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071508$BEA58EFA-5F39-4872-BD92-70FA7B689DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef3803f0f19350c486fbd865c796bf7b40c2c4da","datavalue":{"value":{"entity-type":"item","numeric-id":3929067,"id":"Q3929067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071508$46D64F47-70C5-4C47-B930-4E4F111B8A1C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec6f96b7dc0322b6bf4f0eb3727addc7744ece6f","datavalue":{"value":{"entity-type":"item","numeric-id":793982,"id":"Q793982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9fd988ea487e239a1f708948614910227ce06c5","datavalue":{"value":{"amount":"+0.9167487621307372","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":"Q1071508$240019B2-99FB-44B6-B65F-4BE563986E44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64fbad7da412e44507bb139d7b61f5c6e1e3c5be","datavalue":{"value":{"entity-type":"item","numeric-id":5750862,"id":"Q5750862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f83110074e500c037f75325efdda75bb4105ad9","datavalue":{"value":{"amount":"+0.8481624126434326","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":"Q1071508$E29CE423-EC37-4F43-B7C3-EF884E9238B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61038aa6e0de21f94d280fe6a3941363b87862c3","datavalue":{"value":{"entity-type":"item","numeric-id":4343046,"id":"Q4343046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac6d5915a0c1782bc21e91df8a55cac7b93a420e","datavalue":{"value":{"amount":"+0.8430947661399841","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":"Q1071508$F9F96430-085A-4431-A625-41B2E5B187D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b68e9b39339b6a42cc86b41f85babe46a1dd464","datavalue":{"value":{"entity-type":"item","numeric-id":4411393,"id":"Q4411393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac6d5915a0c1782bc21e91df8a55cac7b93a420e","datavalue":{"value":{"amount":"+0.8430947661399841","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":"Q1071508$47ACCAD4-5542-4C3E-81E8-7101CDC3B564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b2abbcdcea692151f4176c16a5f8faa02b758e3","datavalue":{"value":{"entity-type":"item","numeric-id":5241379,"id":"Q5241379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7f753330bb6bd0e18a469321713c756f80141d0","datavalue":{"value":{"amount":"+0.8425940275192261","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":"Q1071508$892C9DA9-3A41-4210-AE4C-FB8561DA379B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The one-dimensional weighted Voronoi diagram","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_one-dimensional_weighted_Voronoi_diagram"}}}}}