{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:40:44Z","timestamp":1787341244916,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217906"],"award-info":[{"award-number":["CCF-1217906"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1115220"],"award-info":[{"award-number":["IIS-1115220"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1422591"],"award-info":[{"award-number":["IIS-1422591"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422324"],"award-info":[{"award-number":["CCF-1422324"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>In this paper, we study a generalization of the classical Voronoi diagram, called the clustering induced Voronoi diagram (CIVD). Different from the traditional model, CIVD takes as its sites the power set $U$ of an input set $P$ of objects. For each subset $C$ of $P$, CIVD uses an influence function $F(C,q)$ to measure the total (or joint) influence of all objects in $C$ on an arbitrary point $q$ in the space $\\mathbb{R}^d$ and determines the influence-based Voronoi cell in $\\mathbb{R}^d$ for $C$. This generalized model offers a number of new features (e.g., simultaneous clustering and space partition) to the Voronoi diagram which are useful in various new applications. We investigate the general conditions for the influence function which ensure the existence of a small-size (e.g., nearly linear) approximate CIVD for a set $P$ of $n$ points in $\\mathbb{R}^d$ for some fixed $d$. To construct CIVD, we first present a stand-alone new technique, called approximate influence (AI) decomposition, for the general CIVD problem. With only $O(n\\log n)$ time, the AI decomposition partitions the space $\\mathbb{R}^{d}$ into a nearly linear number of cells so that all points in each cell receive their approximate maximum influence from the same (possibly unknown) site (i.e., a subset of $P$). Based on this technique, we develop assignment algorithms to determine a proper site for each cell in the decomposition and form various $(1-\\epsilon)$-approximate CIVDs for some small fixed $\\epsilon&gt;0$. Particularly, we consider two representative CIVD problems, vector CIVD and density-based CIVD, and show that both of them admit fast assignment algorithms; consequently, their $(1-\\epsilon)$-approximate CIVDs can be built in $O(n \\log^{\\max\\{3,d+1\\}}n)$ and $O(n \\log^{2} n)$ time, respectively.<\/jats:p>","DOI":"10.1137\/15m1044874","type":"journal-article","created":{"date-parts":[[2017,11,7]],"date-time":"2017-11-07T14:26:40Z","timestamp":1510064800000},"page":"1679-1711","source":"Crossref","is-referenced-by-count":3,"title":["On Clustering Induced Voronoi Diagrams"],"prefix":"10.1137","volume":"46","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ziyun","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yangwei","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,11,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/2124295.2124330","author":"Andersen R.","year":"2012","journal-title":"Web Search and Data Mining"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"S. Arya and T. Malamatos,\n                      Linear-size approximate Voronoi diagrams\n                      , in Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 147-155.","DOI":"10.1145\/510008.510011"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"S. Arya, T. Malamatos, and D. M. Mount,\n                      Space-efficient approximate Voronoi diagrams\n                      , in Proceedings of the 34th ACM Symposium on Theory of Computing, 2002, pp. 721-730.","DOI":"10.1145\/509907.510011"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/0216006"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"A. Banerjee, C. Krumpelman, S. Basu, R. J. Mooney, and J. Ghosh,\n                      Model-based overlapping Clustering\n                      , in Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2005, pp. 532-537.","DOI":"10.1145\/1081870.1081932"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00320-1"},{"key":"atypb9","first-page":"31","author":"Barequet G.","year":"2011","journal-title":"Science and Engineering"},{"key":"atypb10","first-page":"51","author":"Bonchi F.","year":"2011","journal-title":"IEEE"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"F. Cao, M. Ester, W. Qian, and A. Zhou,\n                      Density-based clustering over an evolving data stream with noise\n                      , in Proceedings of the 6th SIAM International Conference on Data Mining, 2006, pp. 328-339.","DOI":"10.1137\/1.9781611972764.29"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1186\/1479-5876-11-242"},{"key":"atypb14","first-page":"96","author":"Cheilaris P.","year":"2014","journal-title":"Proceedings of LATIN"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001683"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.64"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"Y. Chen and L. Tu,\n                      Density-based clustering for real-time stream data\n                      , in Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007, pp. 133-142.","DOI":"10.1145\/1281192.1281210"},{"key":"atypb18","unstructured":"C. M. Christoudias, R. Urtasun, and T. Darrell,\n                      Multi-View Learning in the Presence of View Disagreement\n                      ,arXiv:1206.3242, 2012."},{"key":"atypb19","unstructured":"G. Cleuziou, L. Martin, and C. Vrain,\n                      PoBOC: An overlapping clustering algorithm\n                      , in Proceedings of the 16th European Conference on Artificial Intelligence, 2004, pp. 440-444."},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"M. T. Dickerson and D. Eppstein,\n                      Animating a continuous family of two-site Voronoi diagrams (and a proof of a bound on the number of regions)\n                      , in Proceedings of the 25th ACM Symposium on Computational Geometry, 2009, pp. 92-93.","DOI":"10.1145\/1542362.1542380"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"M. T. Dickerson and M. T. Goodrich,\n                      Two-site Voronoi diagrams in geographic networks\n                      , in Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2008,doi:10.1145\/1463434.1463504.","DOI":"10.1145\/1463434.1463504"},{"key":"atypb22","first-page":"773","author":"Ding H.","year":"2011","journal-title":"Languages and Programming"},{"key":"atypb23","unstructured":"D. Greene and P. Cunningham,\n                      Multi-view clustering for mining heterogeneous social network data\n                      , in Proceedings of the 31st European Conference on Information Retrieval, Workshop on Information Retrieval over Social Networks, Lecture Notes in Comput. Sci. 5478, Springer, Berlin, 2009."},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"L. Greengard,\n                      The Rapid Evaluation of Potential Fields in Particle Systems\n                      , MIT Press, Cambridge, MA, 1988.","DOI":"10.7551\/mitpress\/5750.001.0001"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1063\/1.4822898"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1126\/science.265.5174.909"},{"key":"atypb27","first-page":"54","volume":"9","author":"Hanniel I.","year":"2010","journal-title":"Trans. Comput. Sci."},{"key":"atypb28","first-page":"94","volume":"2001","author":"S","year":"2001","journal-title":"Proceedings of FOCS"},{"key":"atypb29","first-page":"430","volume":"2012","author":"Har-Peled S.","year":"2012","journal-title":"Proceedings of FOCS"},{"key":"atypb30","unstructured":"D. Hodorkovsky, 2-\n                      Point Site Voronoi Diagrams\n                      , M.Sc. thesis, Technion, Haifa, Israel, 2005."},{"key":"atypb31","first-page":"604","volume":"1998","author":"Indyk P.","year":"1998","journal-title":"Proceedings of STOC"},{"key":"atypb32","first-page":"672","author":"Kriegel H.-P.","year":"2005","journal-title":"Data Mining"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/0210006"},{"key":"atypb34","first-page":"117","author":"Liu A. Y.","year":"2012","journal-title":"Proceedings of the IEEE CS Security and Privacy Workshops"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu,\n                      Spatial Tessellations: Concepts and Applications of Voronoi Diagrams\n                      , 2nd ed., Wiley, New York, 2000.","DOI":"10.1002\/9780470317013"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1095-0"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009745219419"},{"key":"atypb38","first-page":"33","author":"Vyatkina K.","year":"2010","journal-title":"Science and Engineering"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9704-9"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1044874","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:11:10Z","timestamp":1787339470000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1044874"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/15M1044874"],"URL":"https:\/\/doi.org\/10.1137\/15m1044874","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}