An efficient incremental algorithm for generating the characteristic shape of a dynamic set of points in the plane

References

• Acharya, S. and Lee, B.S., 2014. Incremental causal network construction over event streams. Information Sciences, 261, 32–51. doi:10.1016/j.ins.2013.09.022
   Web of Science ®Google Scholar
• Alani, H., Jones, C.B., and Tudhope, D., 2001, Voronoi-based region approximation for geographical information retrieval with gazetteers. International Journal of Geographical Information Science, 15 (4), 287–306. doi:10.1080/13658810110038942
   Web of Science ®Google Scholar
• Anglada, M.V., 1997, An improved incremental algorithm for constructing restricted Delaunay triangulations. Computers & Graphics, 21 (2), 215–223. doi:10.1016/S0097-8493(96)00085-4
   Web of Science ®Google Scholar
• Arampatzis, A., et al., 2006. Web-based delineation of imprecise regions. Computers Environment and Urban Systems, 30 (4), 436–459. doi:10.1016/j.compenvurbsys.2005.08.001
   Web of Science ®Google Scholar
• Babcock, B., et al., 2002. Models and issues in data stream systems. In: Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 3 June, Madison, WI. ACM, 1–16.
   Google Scholar
• Busby, J.R., 1991. BIOCLIM-a bioclimate analysis and prediction system. In: Plant protection quarterly (Australia). Orange: Polymeria Publishing.
   Google Scholar
• Chandrasekaran, S. and Franklin, M.J., 2002. Streaming queries over streaming data. In: Proceedings of the 28th international conference on Very Large Data Bases, 20 August, Hong Kong, 203–214. VLDB Endowment.
   Google Scholar
• Chaudhuri, A.R., Chaudhuri, B.B., and Parui, S.K., 1997, A novel approach to computation of the shape of a dot pattern and extraction of its perceptual border. Computer Vision and Image Understanding, 68 (3), 257–275. doi:10.1006/cviu.1997.0550
   Web of Science ®Google Scholar
• Crooks, A., et al., 2013. # Earthquake: Twitter as a distributed sensor system. Transactions in GIS, 17 (1), 124–147. doi:10.1111/j.1467-9671.2012.01359.x
   Web of Science ®Google Scholar
• De Berg, M., et al., 2000. The doubly-connected edge list. In: Computational geometry. Berlin: Springer-Verlag, 29–33.
   Google Scholar
• Duckham, M., et al., 2008. Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition, 41 (10), 3224–3236. doi:10.1016/j.patcog.2008.03.023
   Web of Science ®Google Scholar
• Edelsbrunner, H., Kirkpatrick, D.G., and Seidel, R., 1983, On the shape of a set of points in the plane. IEEE Transactions on Information Theory, 29 (4), 551–559. doi:10.1109/TIT.1983.1056714
   Web of Science ®Google Scholar
• Ester, M., et al., 1998. Incremental clustering for mining in a data warehousing environment. In: International Conference on Very Large Data Bases, Vol. 98, 24 August, New York. VLDB Endowment, 323–333.
   Google Scholar
• Galton, A. and Duckham, M., 2006. What is the region occupied by a set of points? In: M. Raubal, et al., Geographic information science, 20–23 September. Berlin: Springer, 81–98.
   Google Scholar
• Garai, G. and Chaudhuri, B., 1999, A split and merge procedure for polygonal border detection of dot pattern. Image and Vision Computing, 17 (1), 75–82. doi:10.1016/S0262-8856(98)00089-4
   Web of Science ®Google Scholar
• Goodchild, M.F. and Glennon, J.A., 2010, Crowdsourcing geographic information for disaster response: a research frontier. International Journal of Digital Earth, 3 (3), 231–241. doi:10.1080/17538941003759255
   Web of Science ®Google Scholar
• Guibas, L.J., Knuth, D.E., and Sharir, M., 1992, Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7 (1–6), 381–413. doi:10.1007/BF01758770
   Web of Science ®Google Scholar
• Guo, Q., Kelly, M., and Graham, C.H., 2005, Support vector machines for predicting distribution of Sudden Oak Death in California. Ecological Modelling, 182 (1), 75–90. doi:10.1016/j.ecolmodel.2004.07.012
   Web of Science ®Google Scholar
• Jarvis, R.A., 1973, On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 2 (1), 18–21. doi:10.1016/0020-0190(73)90020-3
   Google Scholar
• Leathwick, J.R., et al., 2005. Using multivariate adaptive regression splines to predict the distributions of New Zealand’s freshwater diadromous fish. Freshwater Biology, 50 (12), 2034–2052. doi:10.1111/j.1365-2427.2005.01448.x
   Web of Science ®Google Scholar
• Li, J., et al., 2005. Semantics and evaluation techniques for window aggregates in data streams. In: Proceedings of the 2005 ACM SIGMOD international conference on Management of data, 14 June, Baltimore, MD, 311–322. ACM.
   Google Scholar
• Lischinski, D., 1994. Incremental delaunay triangulation. Graphics Gems IV, I.5, 47–59.
   Google Scholar
• Manovich, L., 2011, Trending: the promises and the challenges of big social data. Debates in the Digital Humanities, 2, 460–475.
   Google Scholar
• Melkemi, M., 1997. A-shapes of a finite point set. In: Proceedings of the thirteenth annual symposium on Computational geometry, 1 August, Nice, 367–369. ACM.
   Google Scholar
• Melkemi, M. and Djebali, M., 2000, Computing the shape of a planar points set. Pattern Recognition, 33 (9), 1423–1436. doi:10.1016/S0031-3203(99)00124-7
   Web of Science ®Google Scholar
• Mokbel, M.F., et al., 2005. Continuous query processing of spatio-temporal data streams in place. GeoInformatica, 9 (4), 343–365. doi:10.1007/s10707-005-4576-7
   Web of Science ®Google Scholar
• Moreira, A. and Santos, M.Y., 2007. Concave hull: a k-nearest neighbours approach for the computation of the region occupied by a set of points. Lisbon: INSTICC Press.
   Google Scholar
• Motwani, R., et al., 2003. Query processing, resource management, and approximation in a data stream management system. In: CIDR. Stanford, CA: Stanford InfoLab.
   Google Scholar
• Nittel, S., Leung, K.T., and Braverman, A., 2004. Scaling clustering algorithms for massive data sets using data streams. In: B. Salzberg, ed. ICDE, Vol. 4, 830, Boston, MA. Washington, DC: IEEE.
   Google Scholar
• Parker, J.K. and Downs, J.A., 2013, Footprint generation using fuzzy-neighborhood clustering. Geoinformatica, 17 (2), 285–299. doi:10.1007/s10707-012-0152-0
   Web of Science ®Google Scholar
• Peethambaran, J. and Muthuganapathy, R., 2015. A non-parametric approach to shape reconstruction from planar point sets through Delaunay filtering. Computer-Aided Design, 62, 164–175. doi:10.1016/j.cad.2014.12.002
   Web of Science ®Google Scholar
• Phillips, S.J., Anderson, R.P., and Schapire, R.E., 2006, Maximum entropy modeling of species geographic distributions. Ecological Modelling, 190 (3–4), 231–259. doi:10.1016/j.ecolmodel.2005.03.026
   Web of Science ®Google Scholar
• Poser, K. and Dransch, D., 2010, Volunteered geographic information for disaster management with application to rapid flood damage estimation. Geomatica, 64 (1), 89–98.
   Google Scholar
• Sakaki, T., Okazaki, M., and Matsuo, Y., 2010. Earthquake shakes Twitter users: real-time event detection by social sensors. In: Proceedings of the 19th international conference on world wide web, 26 April, Raleigh, NC. ACM, 851–860.
   Google Scholar
• Schade, S., et al., 2013. Citizen-based sensing of crisis events: sensor web enablement for volunteered geographic information. Applied Geomatics, 5 (1), 3–18. doi:10.1007/s12518-011-0056-y
   Google Scholar
• Şeref, O. and Zobel, C.W., 2013, Recursive voids for identifying a nonconvex boundary of a set of points in the plane. Pattern Recognition, 46 (12), 3288–3299. doi:10.1016/j.patcog.2013.05.013
   Web of Science ®Google Scholar
• Tufekci, Z., 2014. Big questions for social media big data: representativeness, validity and other methodological pitfalls. arXiv preprint arXiv:1403.7400. New York: arXiv.
   Google Scholar
• Unal, A., Saygin, Y., and Ulusoy, O.¨., 2006. Processing count queries over event streams at multiple time granularities. Information Sciences, 176 (14), 2066–2096. doi:10.1016/j.ins.2005.10.006
   Web of Science ®Google Scholar
• Vieweg, S., et al., 2010. Microblogging during two natural hazards events: what twitter may contribute to situational awareness. In: Proceedings of the SIGCHI conference on human factors in computing systems, 10 April, Atlanta, GA. ACM, 1079–1088.
   Google Scholar
• Yates, D. and Paquette, S., 2011. Emergency knowledge management and social media technologies: a case study of the 2010 Haitian earthquake. International Journal of Information Management, 31 (1), 6–13. doi:10.1016/j.ijinfomgt.2010.10.001
   Web of Science ®Google Scholar
• Zhang, X., et al., 2014. data stream clustering with affinity propagation. IEEE Transactions on Knowledge and Data Engineering, 26 (7), 1644–1656. doi:10.1109/TKDE.2013.146
   Web of Science ®Google Scholar
• Zhang, X., Furtlehner, C., and Sebag, M., 2008. Data streaming with affinity propagation. In: Machine learning and knowledge discovery in databases. Berlin: Springer, 628–643.
   Google Scholar
• Zhong, X., et al., 2016a. Real-time estimation of wildfire perimeters from curated crowdsourcing. Scientific Reports, 6, article number 24206.
   PubMed Web of Science ®Google Scholar
• Zhong, X., Kealy, A., and Duckham, M., 2016b. Stream Kriging: incremental and recursive ordinary Kriging over spatiotemporal data streams. Computers & Geosciences, 90, 134–143. doi:10.1016/j.cageo.2016.03.004
   Web of Science ®Google Scholar