{"entities":{"Q400517":{"pageid":402284,"ns":120,"title":"Item:Q400517","lastrevid":61608420,"modified":"2026-04-11T00:26:37Z","type":"item","id":"Q400517","labels":{"en":{"language":"en","value":"A note on visibility-constrained Voronoi diagrams"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6333613"}},"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":"Q400517$CFC5C1BF-79ED-4F3A-A58B-1927907CBD13","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"217e0be62a6e737d552dcd928fd757392e9b38d2","datavalue":{"value":{"text":"A note on visibility-constrained Voronoi diagrams","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q400517$282D5C39-6D73-4A11-AEED-9B65BEEBADCC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d22f13e0c710defb00c2b9752517beb827c412d8","datavalue":{"value":"1312.68208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q400517$EBE1D23F-B3D0-4A14-9132-6B6AE5C6D551","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1084ae1d3233d140a2175e96d64da21b3606dc24","datavalue":{"value":{"entity-type":"item","numeric-id":400516,"id":"Q400516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$9AC21405-A4B1-4740-BA70-1F8F9B0F9355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ec8fbe8d522bffba86db602aec04dca122f250a","datavalue":{"value":{"entity-type":"item","numeric-id":243606,"id":"Q243606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$B464D9AD-B90F-4D84-BF2B-2E3536519683","rank":"normal"},{"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":"Q400517$B54D9F5C-AE71-4DE8-AD26-09BF48575E02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"724a8ff23dab918cdb145af8398053f621cc83ea","datavalue":{"value":{"entity-type":"item","numeric-id":1288472,"id":"Q1288472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$BA372BF3-A2F3-46D8-B824-06E651C21495","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$7E99C2C2-7B77-47DB-84CE-92E7445C8EFA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f7a8b27eefbcb795bf06fab270bd2ba67df604cb","datavalue":{"value":{"time":"+2014-08-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q400517$7940FC5B-4AA1-49AB-8E19-5D7DA87A71A9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eb794acc505e18b80db03e306468f4040b4cb567","datavalue":{"value":{"entity-type":"item","numeric-id":306513,"id":"Q306513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$23416778-7FFA-4D16-A2C1-14832CC40EBA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q400517$84D589ED-C0C3-4433-8128-ADF6AB520954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aca3ef8d7fed5a2e532a6e85556c4ddb931de852","datavalue":{"value":"52C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q400517$EBBC6BF0-3E4F-41E2-A763-52EB8F652D5D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5fccff6db9eefb29c95b49f7bd28e48f3d9050b","datavalue":{"value":"6333613","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q400517$20C058F3-29F2-4810-AD75-22C56B132811","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d975c8e13006fbe9b4f6c347ea88f3b06e6e4c7","datavalue":{"value":"Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q400517$4C9AD5FC-4305-4A12-AC58-B3C3088ECDC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bfd605e8d1eec2e403cfe1b9f8fb6385b43b4a0","datavalue":{"value":"visibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q400517$07E5B739-3619-4CAF-B938-0B29DB46A8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a5770b1ed2851a3799695af7284075ed4f2b2f1","datavalue":{"value":"line arrangement","type":"string"},"datatype":"string"},"type":"statement","id":"Q400517$38A0270A-191C-4481-A7C4-00B4B3775402","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"a910160ce3a24e8add80346fd869feb069796ad8","datavalue":{"value":{"entity-type":"item","numeric-id":33596,"id":"Q33596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$48468EC7-FF90-4125-95E3-9521C7B40EA2","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":"Q400517$750693BD-8713-4007-9767-854BF0F0C0F2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3d36ca777e19c0a873fb1db1bebc291569183bde","datavalue":{"value":"https://doi.org/10.1016/j.dam.2014.04.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q400517$07D040C2-7368-43E4-BF28-5911FDD364CE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bcb9b3058fc36d0304e8fd64fbf4de08ed2c0f21","datavalue":{"value":"W2130299606","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q400517$FE716FB9-F594-4636-9783-91D2A8203239","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbc04b6a40c8f3f75600ad0e161103b32fdab533","datavalue":{"value":{"entity-type":"item","numeric-id":4388883,"id":"Q4388883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$7001A576-F94A-4C3C-A770-62F0C8DCDFD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df02f7b211dfbbddb0c4a777ab37df70b0b76b39","datavalue":{"value":{"entity-type":"item","numeric-id":1115602,"id":"Q1115602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$FCEE54C8-120B-4EF9-9C6B-6C0628B30386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"454eeded42bf70a6f1be349b767065463fb1e843","datavalue":{"value":{"entity-type":"item","numeric-id":1209841,"id":"Q1209841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$9B96B111-28DD-4251-8C9F-E0646503F4F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6982a71c4fb0041d09899c6559f70468bf51901c","datavalue":{"value":{"entity-type":"item","numeric-id":2854053,"id":"Q2854053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$CE04E43B-052A-4CDB-87DF-203155B82C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c73bd030b07b1b748a7bd77ee2b610ce83493d1","datavalue":{"value":{"entity-type":"item","numeric-id":3098062,"id":"Q3098062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$5C580DA5-148C-405C-8A11-F2EA3256A887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98686b48b8c2e08b48821e02e53348b40525712c","datavalue":{"value":{"entity-type":"item","numeric-id":1115601,"id":"Q1115601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$830DE9FA-A12E-4FC0-A198-031DF5BD338C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec8b4d9c8ab43c964ebd317432f831e9e03ea515","datavalue":{"value":{"entity-type":"item","numeric-id":917017,"id":"Q917017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$A4B33862-2C2C-4D2D-82F7-A0A341A795CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$5ACD9872-5444-4548-9038-352D8CEFAE17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba1eef9a8de19b57864dc87d5c058554f9d6c7cf","datavalue":{"value":{"entity-type":"item","numeric-id":582900,"id":"Q582900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$5DA8160C-FE73-4329-97BB-3C5BC2C0E5B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"164780db09699ea2d42a7163a7d016bde689dd7e","datavalue":{"value":{"entity-type":"item","numeric-id":582901,"id":"Q582901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$051E76E8-1A60-4576-9A08-064E58D89B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63081d5d792f3a683ae560aa1f30e7797c4c4d9c","datavalue":{"value":{"entity-type":"item","numeric-id":2445868,"id":"Q2445868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$4A6B837F-3D86-4788-8194-8D0D209E4F0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e8ae7e1c33095f730b454b2145e23f382a24577","datavalue":{"value":{"entity-type":"item","numeric-id":4003725,"id":"Q4003725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$3A880D6C-C717-4806-B393-A53A27BFF8D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bd53defd1b885afb6fd232d4d93b234faab9514","datavalue":{"value":{"entity-type":"item","numeric-id":4268866,"id":"Q4268866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$A9C4EBD2-CA1A-4F7C-987A-F141CA761999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cceec15e0bf6f1544f3e1864012ec31a05ee6eb","datavalue":{"value":{"entity-type":"item","numeric-id":1078807,"id":"Q1078807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$8A73A154-9A5D-4EA9-9457-4D1D9AA38F12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf272138c0f0cb723f48929502d668d4ad806845","datavalue":{"value":{"entity-type":"item","numeric-id":5687652,"id":"Q5687652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$F42E75A1-DDC2-4D60-934B-0F851A28DAD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bac3848926032114bebb2881bb374975f7165251","datavalue":{"value":{"entity-type":"item","numeric-id":2864864,"id":"Q2864864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$DACBA9A0-633A-4085-8AAB-C76F74041A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"787d0490e801adb6715b441395f82f2f20382d74","datavalue":{"value":{"entity-type":"item","numeric-id":794651,"id":"Q794651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$C5F2304B-39D6-4403-88C1-CCD476145EEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54c78faa2f7496ed3f56a013d7ae70225c3e1749","datavalue":{"value":{"entity-type":"item","numeric-id":1388136,"id":"Q1388136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q400517$6C919581-74C8-4EF7-85E3-ED5423C19051","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5fc595e6f6ec6025b7fe8595ca299415aa82ef7f","datavalue":{"value":"10.1016/J.DAM.2014.04.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q400517$FD622B68-D42E-4BD3-84F5-A1F1C1CE4904","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e1fdfe3c5018468caa99723f44ede467a60d3fa","datavalue":{"value":"The authors introduce \\textit{baseline Voronoi diagrams} as follows. Given are finitely many points \\(p_1,\\dots,p_n\\) in the Euclidean plane \\(\\mathbb R^2\\) and closed halfspaces \\(H_1,\\dots,H_n\\) of \\(\\mathbb R^2\\) such that, for each \\(i\\), the point \\(p_i\\) belongs to the boundary of \\(H_i\\). A point \\(p_i\\) is said to see a point \\(x\\) of \\(\\mathbb R^2\\) if \\(x\\) lies in \\(H_i\\) and, for every \\(j \\in \\{1,\\dots,n\\}\\setminus \\{i\\}\\), the segment joining \\(p_i\\) and \\(x\\) does not intersect the boundary of \\(H_j\\). With each \\(p_i\\) one associates the set \\(\\mathrm{reg}(p_i)\\) of all points \\(x\\) seen by \\(p_i\\) and such that no point \\(p_j\\) with \\(j \\in \\{1,\\dots,n\\} \\setminus \\{i\\}\\) that sees \\(x\\) is closer to \\(x\\). The baseline Voronoi diagram for the data \\(p_1,\\dots,p_n\\), \\(H_1,\\dots,H_n\\) is composed of the regions \\(\\mathrm{reg}(p_1),\\dots,\\mathrm{reg}(p_n)\\). The union of the boundaries of the latter regions can be viewed as plane graph (with edges being line segments) so that one can speak (using the standard terminology for plane graphs) about vertices, edges and faces of baseline Voronoi diagrams.NEWLINENEWLINEThe main result of the paper asserts that the baseline Voronoi diagram for \\(n\\) points has \\(O(n)\\) faces and \\(O(n^{4/3})\\) edges and vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q400517$C4262E18-FABD-4D3D-BB5D-C3B216B262D3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"663d3cf98b93903237b5794a405a0ecba2af8e4b","datavalue":{"value":{"entity-type":"item","numeric-id":1388136,"id":"Q1388136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c66bc57c1433b715d4db95266994b558d769c636","datavalue":{"value":{"amount":"+0.8276972770690918","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":"Q400517$471278FA-2F6F-472D-9164-6A9B5DCA30AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17e24c907ddc4f0284099881992cf2e28ea76b28","datavalue":{"value":{"entity-type":"item","numeric-id":2897980,"id":"Q2897980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6778e7c848f0f5c7d82c807c34fa4b2bcca65c8e","datavalue":{"value":{"amount":"+0.8097043633460999","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":"Q400517$FF9DE6D0-FA82-4CF3-8D54-E03C440A2FE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6768339f32228de0bbc335ace0cef3905186fb9f","datavalue":{"value":{"entity-type":"item","numeric-id":2445868,"id":"Q2445868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"254fd6360f3abc92353ae9c2063dad65f95043fc","datavalue":{"value":{"amount":"+0.8016292452812195","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":"Q400517$6BBAC16C-E017-458B-BDEE-D991D66331C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a61289510f33c5ee63338a17c91cd56a87f6f36","datavalue":{"value":{"entity-type":"item","numeric-id":1206436,"id":"Q1206436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b7063882625b06c5fa11aad469df1b632fb9277","datavalue":{"value":{"amount":"+0.7757031917572021","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":"Q400517$967315ED-7068-4097-9DD9-C06280625C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8f78f6dfaf847409098d427b5513bf9488eb73d","datavalue":{"value":{"entity-type":"item","numeric-id":4580129,"id":"Q4580129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e262f42f6c5f0f13102d6eff9d09b0a9b74191c","datavalue":{"value":{"amount":"+0.7595967054367065","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":"Q400517$23C40FFC-ABD6-4552-866B-4B2D982BD91D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on visibility-constrained Voronoi diagrams","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_visibility-constrained_Voronoi_diagrams"}}}}}