{"entities":{"Q1947994":{"pageid":1958736,"ns":120,"title":"Item:Q1947994","lastrevid":51706169,"modified":"2026-01-19T14:29:52Z","type":"item","id":"Q1947994","labels":{"en":{"language":"en","value":"Dynamic well-spaced point sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6159342"}},"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":"Q1947994$AB143AD5-7CDB-43FC-8358-8A112C865904","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"26204d80753af39490a1ebf8629658727d4c3dd6","datavalue":{"value":{"text":"Dynamic well-spaced point sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1947994$BBFF39A9-07CE-4ACC-AC56-A4F4206254CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d1ae638fedc2d8a75d2c26dfac3816e2ecb7a62","datavalue":{"value":"1267.65022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947994$63A61F68-F81B-49A7-8460-147E4D24C0A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d3c9d76b381e32901aa1410bcb6eb37917cf64be","datavalue":{"value":{"entity-type":"item","numeric-id":1799302,"id":"Q1799302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$38134092-CEBE-45EB-9E5C-538B8061D75B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e96142b73d3c4d30fadb0a0a62797a37eff13ee","datavalue":{"value":{"entity-type":"item","numeric-id":633111,"id":"Q633111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$3E340748-6264-4553-B7DE-97592614FAD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a936e88da9c6e25d563dfaf5c11ebb62a29c2bc8","datavalue":{"value":{"entity-type":"item","numeric-id":1947992,"id":"Q1947992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$3FDF7412-E850-48F4-AEC1-19A44BAF643D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1520d2858dc415c835297beff2af58ebcd5d9b85","datavalue":{"value":{"entity-type":"item","numeric-id":1947993,"id":"Q1947993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$48EAA55D-FBD4-48B9-9D80-99617F6579DD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$A10A152A-6ADD-4680-BC3C-72672E998169","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae17c4ecf184e2afd3c8b133626fdd9ae2ee388a","datavalue":{"value":{"time":"+2013-04-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1947994$9274C726-8328-4788-9352-C18AA73D6A6E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c8be0bd0e419bb598151d0005c536ca51684bd98","datavalue":{"value":"The authors consider the dynamic well-spaced point set problem, which requires constructing a well-spaced superset of a dynamically changing input set, e.g., as input points are inserted or deleted. They present a dynamic algorithm that allows inserting/deleting points into/from the input in \\(O(\\log \\Delta )\\) time, where \\(\\Delta\\) is the geometric spread, a natural measure that yields an \\(O(\\log n)\\) bound when input points are represented by log-size words. It is shown that this algorithm is time-optimal by proving a lower bound of \\(\\Omega (\\log \\Delta )\\) for a dynamic update. Also, they show that this algorithm maintains size-optimal outputs: the well-spaced supersets are within a constant factor of the minimum possible size. The asymptotic bounds in the paper's results work in any constant dimensional space. Experiments with a preliminary implementation indicate that dynamic changes may be performed with considerably greater efficiency than re-constructing a well-spaced point set from a scratch. These are the first time- and size-optimal algorithms for dynamically maintaining well-spaced point sets.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947994$D1E1D5BE-20AB-4043-915F-DC525DA028BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947994$18B7FB83-47E3-483B-BB1D-6B63CA9D8D6B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a3c6a6cf0c07aacf08309aac73a106ccf7ec29c3","datavalue":{"value":"6159342","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947994$F8534DB8-A425-437D-9D2D-C9080CB25B43","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dff30a2dd7326738aa0549384e71cca92c7bd2ae","datavalue":{"value":"well-spaced point set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947994$7D79D846-6AFC-4DAD-871B-AF45E24D9C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfc9b077a4d7e3b8ac28efaa408f509efd01ffac","datavalue":{"value":"clipped Voronoi cell","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947994$0D5D6B0A-BFAC-442A-AF37-EFB6A6D78F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"677316bedf31e8dab1deb19f92b996c4a8d81f3e","datavalue":{"value":"mesh refinement","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947994$34568F02-C0DC-4F16-B408-72E467549F77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96d03654aaa010e487a5baf71c20a3ea9409b27f","datavalue":{"value":"dynamic stability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947994$0767275C-E659-4A79-9120-139A3569449C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68be47acc56b60a10010a295732a1aa0ae31b02b","datavalue":{"value":"self-adjusting computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947994$4904B298-6955-4F28-96D7-B3C8F37F0727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d74cb5419439f42eb1ba8891c8722bd3702922d","datavalue":{"value":"numerical examples","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947994$55E2C8BD-8015-41C4-99C6-4647A460201A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a919579df661e5c65ccdc4a7c6703c3098028d3","datavalue":{"value":"dynamic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1947994$B8AE2142-D71C-47BE-A946-44AA71737EF7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"90d441912c89e782d7786086a948a0e077f5bf58","datavalue":{"value":{"entity-type":"item","numeric-id":300567,"id":"Q300567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$326F2EDB-EB14-4182-AE75-239AA8D7EE8A","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"2ee1da4c6d65c536d448356b5fbc699a09250e89","datavalue":{"value":{"entity-type":"item","numeric-id":19906,"id":"Q19906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$4202966B-2025-4E1F-8A0F-5D495FC74E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"948b795ec8c8e96daf96f731aa8e8c2afef77d41","datavalue":{"value":{"entity-type":"item","numeric-id":23610,"id":"Q23610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$32B30536-595F-4F1B-9ED4-BC0989ADA42F","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":"Q1947994$4F3B5BDA-75D4-434B-BD92-ED7763637768","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea983c4d0570c2dbc7f5c4265210cc7f527d5cfe","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2012.11.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q1947994$0A95CCE1-58E9-41A7-80A3-81F66168C1ED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"528641a894038ef5b3cc6edd2c59481f6bc683e1","datavalue":{"value":"W2202662702","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947994$E5D5B056-095E-4CEA-9CDF-084B1C6C5FB0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"00174e7ddae86e038817491cd765a0a20f7b7f02","datavalue":{"value":{"entity-type":"item","numeric-id":3541071,"id":"Q3541071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$D270132D-4BB5-4237-9CEF-3A0EE1EA746A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec0e4066bcd48214870bacc5c1a3a873315dce6a","datavalue":{"value":{"entity-type":"item","numeric-id":5405896,"id":"Q5405896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$8264823F-6240-4118-AC2E-B38EAE84879E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71d23feb1bd5d04c8ae8d0e5cc49859fcfc1bc14","datavalue":{"value":{"entity-type":"item","numeric-id":5442552,"id":"Q5442552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$D00B83C0-ECF1-4CB5-A63A-7563DB47A7C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef96dd79126804bc8df7866dd4eb8c968fed3308","datavalue":{"value":{"entity-type":"item","numeric-id":1329150,"id":"Q1329150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$C8FD84F3-426B-427E-A4FF-0A0C5B28BD53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b06effdde7dfe79d99b9664e143d556fb9a2c6c5","datavalue":{"value":{"entity-type":"item","numeric-id":1192610,"id":"Q1192610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$247D1EF5-8F9A-4B6A-B6CA-8182B52A814B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a456b18fc809756f004c41590367aab0d04c914b","datavalue":{"value":{"entity-type":"item","numeric-id":2946996,"id":"Q2946996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$4E003DB0-A79C-4A02-8942-F106757E7038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43b98c6ccd6f970464edbcf4ed2c02345f1dd394","datavalue":{"value":{"entity-type":"item","numeric-id":686138,"id":"Q686138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$9B006788-C194-4185-BEF5-4B57A7409701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0273b9f2491c31406c0ff3339fc0ea8ddb68d7e9","datavalue":{"value":{"entity-type":"item","numeric-id":5370616,"id":"Q5370616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$BDD044DC-D6DB-4483-AB24-8D7DFD059A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b7c19fe9f933eecb297bd8e17aaf4765ab195d4","datavalue":{"value":{"entity-type":"item","numeric-id":5442554,"id":"Q5442554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$5E46BCAA-9FC0-4C7F-A410-6EE2F088E064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73f9b8a37cfced3d2d633f5829611afc50037fe2","datavalue":{"value":{"entity-type":"item","numeric-id":5261517,"id":"Q5261517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$D4AFA440-519B-41F7-A8EB-DBA021D39B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83902ebce4503dc4a1fd2d1588028db0cb96c700","datavalue":{"value":{"entity-type":"item","numeric-id":2768269,"id":"Q2768269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$8A5634C3-570B-4340-8D34-3AEE2ADFF387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e0332116d1a395e8ccad75ce610c4aa12705c55","datavalue":{"value":{"entity-type":"item","numeric-id":1809120,"id":"Q1809120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$819F89A2-C10E-40FB-AE8C-AC7B3425ECC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ddf21c51588a354facefe57df1b8ebfd2ac01ae","datavalue":{"value":{"entity-type":"item","numeric-id":4837546,"id":"Q4837546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$C5FE419F-1106-4684-A7C4-27DBFED0BBE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4f68b875e3ff1e0e8868a66c62d38005d65204f","datavalue":{"value":{"entity-type":"item","numeric-id":1602942,"id":"Q1602942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$E6882D38-FD06-47F6-B127-3A0205E736D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80dc9cd534c3cae85f98a04b0e026b7ef216df95","datavalue":{"value":{"entity-type":"item","numeric-id":3430330,"id":"Q3430330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1947994$968DC995-9AC6-429C-834A-9E27D7541160","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"10b95ffa7a0359039bd65a526b0d5b8d917f13a0","datavalue":{"value":"10.1016/J.COMGEO.2012.11.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1947994$29321013-5D59-4F1A-A24D-A8990FFF1ACE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f4958eb62c9fd8e08cbfb352b6f712658dcdab5","datavalue":{"value":{"entity-type":"item","numeric-id":5405896,"id":"Q5405896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a11d7d9682ff66ef39f38164dcbc2880f7ea22b1","datavalue":{"value":{"amount":"+0.9360029697418212","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":"Q1947994$13E2D419-2AA9-4104-9FBE-027922E198A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a64f9181f5257b7051b83a9c1307e233067a25dd","datavalue":{"value":{"entity-type":"item","numeric-id":5920251,"id":"Q5920251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc050f0531ae20073352b05815ebb485b5564c39","datavalue":{"value":{"amount":"+0.7860053777694702","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":"Q1947994$BEBAF23F-86B5-407A-837F-7AB62ED720C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23dfad2ca21b3f66217262d6f8b1eba0ad5b6b28","datavalue":{"value":{"entity-type":"item","numeric-id":1189290,"id":"Q1189290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"198234c9b206eae8b501f778b9f38bfe52261c42","datavalue":{"value":{"amount":"+0.785890519618988","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":"Q1947994$150B6D1F-AE66-4F7A-86DC-2E800FE81F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6d409575edb4135b4e70deefad436609747b19f","datavalue":{"value":{"entity-type":"item","numeric-id":1346130,"id":"Q1346130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a264d3095c55d4e4e490ee598c81b6a58e53960","datavalue":{"value":{"amount":"+0.7789088487625122","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":"Q1947994$59432E9D-5A08-4602-85D9-C98419D62995","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e33d87e6c76a81c315056ef5771aa06b6f84d87","datavalue":{"value":{"entity-type":"item","numeric-id":5174489,"id":"Q5174489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a76b66c20c100f5517677c230beb5421a6b41bed","datavalue":{"value":{"amount":"+0.7732567191123962","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":"Q1947994$4B9A0DC3-6206-4B24-AFC0-20EA995736F3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1947994","badges":[]}}}}}