CD-graph: planar graph representation for spatial adjacency and neighbourhood relation with constraints

References

• Chen, B.Y., et al., 2012. Reliable shortest path finding in stochastic networks with spatial correlated link travel times. International Journal of Geographical Information Science, 26 (2), 365–386.
   Web of Science ®Google Scholar
• Chen, J., Qiao, C., and Zhao, R., 2004a. A Voronoi interior adjacency-based approach for generating a contour tree. Computers & Geosciences, 30 (4), 355–367.
   Web of Science ®Google Scholar
• Chen, J., Zhao, R., and Li, Z., 2004b. Voronoi-based k-order neighbour relations for spatial analysis. ISPRS Journal of Photogrammetry and Remote Sensing, 59 (1–2), 60–72.
   Web of Science ®Google Scholar
• Chew, L.P., 1989. Constrained delaunay triangulations. Algorithmica, 4 (1), 97–108.
   Web of Science ®Google Scholar
• Cignoni, P., Montani, C., and Scopigno, R., 1998. DeWall: a fast divide and conquer Delaunay triangulation algorithm in Ed. Computer-Aided Design, 30 (5), 333–341.
   Web of Science ®Google Scholar
• De Berg, M., et al., 2008. Computational geometry: algorithms and applications. 3rd ed. Germany: Springer-Verlag.
   Google Scholar
• De Floriani, L., Magillo, P., and Puppo, E., 2000. Applications of computational geometry to geographic information systems. In: J.R. Sack and J. Urrutia, eds. Handbook of computational geometry. Amsterdam: North-Holland, 333–388.
   Google Scholar
• Domiter, V., 2004. Constrained Delaunay triangulation using plane subdivision. In: 8th central European seminar on computer graphics (CESCG’04), Budmerice, Slovakia: Citeseer, 105–110.
   Google Scholar
• Domiter, V. and Zalik, B., 2008. Sweep-line algorithm for constrained Delaunay triangulation. International Journal of Geographical Information Science, 22 (4), 449–462.
   Web of Science ®Google Scholar
• Estivill-Castro, V. and Lee, I., 2000a. AUTOCLUST: Automatic clustering via boundary extraction for mining massive point data sets. In: 2000 5th international conference on geo-computation, 23–25 August 2000, Kent, UK: University of Greenwich, 23–25.
   Google Scholar
• Estivill-Castro, V. and Lee, I., 2000b. AUTOCLUST+: Automatic clustering of point-data sets in the presence of obstacles. In: 2000 international workshop on temporal and spatial and spatio-temporal data mining (TSDM’00), 12 September, Lyon, France. Berlin: Springer, 133–146.
   Google Scholar
• Estivill-Castro, V. and Lee, I., 2001. Fast spatial clustering with different metrics and in the presence of obstacles. In: 9th ACM international symposium on advances in geographic information systems, 9–10 November, Atlanta, Georgia, USA, 142–147.
   Google Scholar
• Estivill-Castro, V. and Lee, I., 2004. Clustering with obstacles for geographical data mining. ISPRS Journal of Photogrammetry and Remote Sensing, 59 (1–2), 21–34.
   Web of Science ®Google Scholar
• Fortune, S., 1987. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2 (2), 153–174.
   Web of Science ®Google Scholar
• Frenkel, G., et al., 2009. Topological analysis of foams and tetrahedral structures. Advanced Engineering Materials, 11 (3), 169–176.
   Web of Science ®Google Scholar
• Gold, C.M. and John’s, St. 1989. Voronoi diagrams and spatial adjacency. In: 1989 national conference on GIS: challenge for the 1990s, 5–8 March, Ottawa, Canada, 1309–1316.
   Google Scholar
• Gudmundsson, J., Haverkort, H.J., and Van Kreveld, M., 2005. Constrained higher order Delaunay triangulations. Computational Geometry, 30 (3), 271–277.
   Web of Science ®Google Scholar
• Guibas, L. and Stolfi, J., 1985. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4 (4), 74–123.
   Google Scholar
• Hersperger, A.M., 2006. Spatial adjacencies and interactions: neighborhood mosaics for landscape ecological planning. Landscape and Urban Planning, 77 (3), 227–239.
   Web of Science ®Google Scholar
• Karasick, M., Lieber, D., and Nackman, L.R., 1991. Efficient Delaunay triangulation using rational arithmetic. ACM Transactions on Graphics (TOG), 10 (1), 71–91.
   Web of Science ®Google Scholar
• Klette, R. and Rosenfeld, A., 2004. Adjacency graphs. In: Digital Geometry: Geometric Methods for Digital Picture Analysis, T. Cox, Ed. San Francisco: Morgan Kaufmann, 117–157.
   Google Scholar
• Lee, D. and Lee, J., 2009. Dynamic dissimilarity measure for support-based clustering. IEEE Transactions on Knowledge and Data Engineering, 22 (6), 900–905.
   Web of Science ®Google Scholar
• Li, J., et al., 2008. Topological spatial relation calculation in constrained Delaunay triangulation: an algebraic method. In: 2008 geoinformatics and joint conference on GIS and built environment: advanced spatial data models and analyses, 28–29 June, Guangzhou, China: SPIE, 1–14.
   Google Scholar
• Maur, P. and Kolingerov, I., 2004. The employment of regular triangulation for constrained Delaunay triangulation. In: International conference on computational science and its applications (ICSSA’04), 14–17 May, Assisi, Italy, 198–206.
   Google Scholar
• Merrett, T.H., 2005. Quad-edge data structures in two and three dimensions. Canada: Montreal.
   Google Scholar
• Mostafavi, M.A., Gold, C., and Dakowicz, M., 2003. Delete and insert operations in Voronoi/Delaunay methods and applications. Computers & Geosciences, 29 (4), 523–530.
   Web of Science ®Google Scholar
• Nam, N.M., Kiem, H.V., and Nam, N.V., 2009. A fast algorithm for constructing constrained Delaunay triangulation. In: 2009 IEEE-RIVF international conference on computing and communication technologies: research, innovation and vision for the future (RIVF 2009), 13–17 July, Danang, Vietnam: IEEE Computer Society, 1–4.
   Google Scholar
• Nedas, K.A. and Egenhofer, M.J., 2008. Integral vs. separable attributes in spatial similarity assessments. Lecture Notes in Computer Science: Spatial Cognition VI. Learning, Reasoning, and Talking about Space, Berlin: Springer-Verlag, 5248, 295–310.
   Google Scholar
• Qiao, C., et al., 2005. A method for generating contour tree based on Voronoi interior adjacency. Geo-Spatial Information Science(Quarterly), 8 (4), 287–290.
   Google Scholar
• Ramirez-Padron, R., et al., 2010. Similarity kernels for nearest neighbor-based outlier detection. Lecture Notes in Computer Science: Advances in Intelligent Data Analysis, 6065, 159–170.
   Google Scholar
• Ruiz, C., Spiliopoulou, M., and Menasalvas, E., 2007. C-DBSCAN: density-based clustering with constraints. In: 2007 11th international conference on rough sets, fuzzy sets, data mining, and granular computer(RSFDGrC’07), 14–17 May, Toronto, Canada: Springer Verlag, 216–223.
   Google Scholar
• Shewchuk, J.R., 2000. Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations. In: 2000 16th annual symposium on computational geometry, 12–14 June, Kowloon, Hong Kong: ACM Press, 350–359.
   Google Scholar
• Silveira, R.I. and Van Kreveld, M., 2009. Towards a definition of higher order constrained Delaunay triangulations. Computational Geometry: Theory and Applications, 42 (4), 322–337.
   Web of Science ®Google Scholar
• Tung, A.K.H., Hou, J., and Han, J., 2000. COE: clustering with obstacles entities, a preliminary study. In: 2000 international conference on knowledge discovery and data mining (PAKDD’00), Kyoto, Japan, April 18–20, 2000, 165–168
   Google Scholar
• Tung, A.K.H., Hou, J., and Han, J., 2001. Spatial clustering in the presence of obstacles. In: 2001 17th international conference on data engineering, 2–6 April, Heidelberg, Germany, 359–367.
   Google Scholar
• Wang, X., Rostoker, C., and Hamilton, H.J., 2004. Density-based spatial clustering in the presence of obstacles and facilitators. LNCS: knowledge discovery in databases (PKDD’04), 3202, 446–458.
   Web of Science ®Google Scholar
• Wei, W., et al., 2009. An intelligent method of detecting multi-factors neighborhood relation based on constrained Delaunay triangulation. In: 2009 WRI Global Congress on Intelligent Systems (GCIS 2009), 19–21 May, Xiamen, China: IEEE Computer Society, 248–252.
   Google Scholar
• Zaiane, O.R. and Lee, C.-H., 2002a. Clustering spatial data in the presence of obstacles: a density-based approach. In: 2002 sixth international symposium on database engineering & applications (IDEAS’02), 17–19 July, Edmonton, AB, Canada, 214–223.
   Google Scholar
• Zaiane, O.R. and Lee, C.-H., 2002b. Clustering spatial data when facing physical constraints. In: 2002 2nd IEEE international conference on data mining (ICDM’02), 9–12 December, Maebashi City, Japan, 737–740.
   Google Scholar
• Zalik, B. and Kolingerova, I., 2003. An incremental construction algorithm for Delaunay triangulation using the nearest-point paradigm. International Journal of Geographical Information Science, 17 (2), 119–138.
   Web of Science ®Google Scholar
• Zhao, R., Chen, J., and Li, Z., 2002. K-order spatial neighbours based on Voronoi diagram: description, computation and applications. International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences, 34 (4), 10–15.
   Google Scholar
• Zhu, B., 2003. On Lawson’s oriented walk in random Delaunay triangulations. Lecture Notes In Computer Science, 2751, 222–233.
   Google Scholar
• Zhu, Y.J. and Yan, L., 2010. An improved algorithm of constrained Delaunay triangulation based on the diagonal exchange. In: 2010 2nd international conference on future computer and communication (ICFCC 2010), 21–24 May, Wuhan, China: IEEE Computer Society, V1827–V1830.
   Google Scholar