{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T07:28:13Z","timestamp":1779348493610,"version":"3.51.4"},"reference-count":39,"publisher":"MDPI AG","issue":"18","license":[{"start":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T00:00:00Z","timestamp":1568246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002560","name":"Soonchunhyang University","doi-asserted-by":"publisher","award":["NA"],"award-info":[{"award-number":["NA"]}],"id":[{"id":"10.13039\/501100002560","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2018R1D1A3B07041729"],"award-info":[{"award-number":["2018R1D1A3B07041729"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In spatial data with complexity, different clusters can be very contiguous, and the density of each cluster can be arbitrary and uneven. In addition, background noise that does not belong to any clusters in the data, or chain noise that connects multiple clusters may be included. This makes it difficult to separate clusters in contact with adjacent clusters, so a new approach is required to solve the nonlinear shape, irregular density, and touching problems of adjacent clusters that are common in complex spatial data clustering, as well as to improve robustness against various types of noise in spatial clusters. Accordingly, we proposed an efficient graph-based spatial clustering technique that employs Delaunay triangulation and the mechanism of DBSCAN (density-based spatial clustering of applications with noise). In the performance evaluation using simulated synthetic data as well as real 3D point clouds, the proposed method maintained better clustering and separability of neighboring clusters compared to other clustering techniques, and is expected to be of practical use in the field of spatial data mining.<\/jats:p>","DOI":"10.3390\/s19183926","type":"journal-article","created":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T10:56:06Z","timestamp":1568285766000},"page":"3926","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Delaunay Triangulation-Based Spatial Clustering Technique for Enhanced Adjacent Boundary Detection and Segmentation of LiDAR 3D Point Clouds"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8196-1089","authenticated-orcid":false,"given":"Jongwon","family":"Kim","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, Soonchunhyang University, Asan 31538, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5162-1745","authenticated-orcid":false,"given":"Jeongho","family":"Cho","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Soonchunhyang University, Asan 31538, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,9,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Alelyani, S., Tang, J., and Liu, H. (2018). Feature selection for clustering: A review. Data Clustering, Taylor & Francis Group.","DOI":"10.1201\/9781315373515-2"},{"key":"ref_2","first-page":"59","article-title":"A survey on density based clustering algorithms for mining large spatial databases","volume":"31","author":"Parimala","year":"2011","journal-title":"Int. J. Adv. Sci. Technol."},{"key":"ref_3","first-page":"281","article-title":"Some methods for classification and analysis of multivariate observations","volume":"Volume 1","author":"MacQueen","year":"1967","journal-title":"Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability"},{"key":"ref_4","unstructured":"Ester, M., Kriegel, H.P., Sander, J., and Xu, X. (1996, January 2\u20134). A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD\u201996), Portland, OR, USA."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kellner, D., Klappstein, J., and Dietmayer, K. (2012, January 3\u20137). Grid-based DBSCAN for clustering extended objects in radar data. Proceedings of the 2012 IEEE Intelligent Vehicles Symposium, Alcale de Henares, Spain.","DOI":"10.1109\/IVS.2012.6232167"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3182","DOI":"10.1109\/TIP.2016.2559803","article-title":"DSets-DBSCAN: A parameter-free clustering algorithm","volume":"25","author":"Hou","year":"2016","journal-title":"IEEE Trans. Image Process."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Wang, X., and Hamilton, H.J. (2003). DBRS: A density-based spatial clustering method with random sampling. Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer.","DOI":"10.1007\/3-540-36175-8_56"},{"key":"ref_8","unstructured":"Ng, A.Y., Jordan, M.I., and Weiss, Y. (2001, January 3\u20138). On spectral clustering: Analysis and an algorithm. Proceedings of the 14th International Conference on Neural Information Processing Systems, British Columbia, Canada."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi","year":"2000","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Weiss, Y. (1999, January 20\u201327). Segmentation using eigenvectors: A unifying view. Proceedings of the Seventh IEEE International Conference on Computer Vision, Kerkyra, Greece.","DOI":"10.1109\/ICCV.1999.790354"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"451","DOI":"10.3233\/IDA-2002-6505","article-title":"Detecting graph-based spatial outliers","volume":"6","author":"Shekhar","year":"2002","journal-title":"Intell. Data Anal."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/j.compenvurbsys.2011.02.003","article-title":"An adaptive spatial clustering algorithm based on Delaunay triangulation","volume":"35","author":"Deng","year":"2011","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.cageo.2017.08.014","article-title":"A density-based clustering algorithm for earthquake zoning","volume":"110","author":"Scitovski","year":"2018","journal-title":"Comput. Geosci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1109\/LGRS.2012.2231662","article-title":"A spatial clustering method with edge weighting for image segmentation","volume":"10","author":"Li","year":"2013","journal-title":"IEEE Geosci. Remote Sens. Lett."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Aksac, A., \u00d6zyer, T., and Alhajj, R. (2019). CutESC: Cutting Edge Spatial Clustering Technique based on Proximity Graphs. Pattern Recognit., 96.","DOI":"10.1016\/j.patcog.2019.06.014"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1016\/j.patrec.2008.01.028","article-title":"Effective clustering and boundary detection algorithm based on Delaunay triangulation","volume":"29","author":"Liu","year":"2008","journal-title":"Pattern Recognit. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1147","DOI":"10.14358\/PERS.79.12.1147","article-title":"3D Tree reconstruction from simulated small footprint waveform lidar","volume":"79","author":"Wu","year":"2013","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Wu, X., Jiang, H., and Chen, C. (2018). SCMDOT: Spatial Clustering with Multiple Density-Ordered Trees. ISPRS Int. J. Geo-Inf., 6.","DOI":"10.3390\/ijgi6070217"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1016\/j.patcog.2009.07.010","article-title":"A graph-theoretical clustering method based on two rounds of minimum spanning trees","volume":"43","author":"Zhong","year":"2010","journal-title":"Pattern Recognit."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"3336","DOI":"10.1016\/j.eswa.2008.01.039","article-title":"A simple and fast algorithm for K-medoids clustering","volume":"36","author":"Park","year":"2009","journal-title":"Expert Syst. Appl."},{"key":"ref_21","unstructured":"Ng, R.T., and Han, J. (1994, January 12\u201315). Efficient and Effective Clustering Methods for Spatial Data Mining. Proceedings of the VLDB, Santiago, Chile."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Zhang, T., Ramakrishnan, R., and Livny, M. (1996, January 4\u20136). BIRCH: An efficient data clustering method for very large databases. Proceedings of the ACM SIGMOD International Conference on Management of Data, Montreal, QC, Canada.","DOI":"10.1145\/233269.233324"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Khan, K., Rehman, S.U., Aziz, K., Fong, S., and Sarasvady, S. (2014, January 17\u201319). DBSCAN: Past, present and future. Proceedings of the Fifth International Conference on the Applications of Digital Information and Web Technologies (ICADIWT 2014), Bangalore, India.","DOI":"10.1109\/ICADIWT.2014.6814687"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Ankerst, M., Breunig, M.M., Kriegel, H.P., and Sander, J. (June, January 31). OPTICS: Ordering points to identify the clustering structure. Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data (SIGMOD\u201999), New York, NY, USA.","DOI":"10.1145\/304182.304187"},{"key":"ref_25","unstructured":"Hinneburg, A., and Gabriel, H.H. (2007). Denclue 2.0: Fast clustering based on kernel density estimation. International Symposium on Intelligent Data Analysis, Springer."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","year":"2007","journal-title":"Stat. Comput."},{"key":"ref_27","unstructured":"Estivill-Castro, V., and Lee, I. (2000, January 23\u201325). AUTOCLUST: Automatic Clustering via Boundary Extraction for Mining Massive Point-Data Sets. Proceedings of the 5th International Conference on Geocomputation, Greenwich, UK."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0198-9715(01)00044-8","article-title":"Argument free clustering for large spatial point-data sets via boundary extraction from Delaunay Diagram","volume":"26","author":"Lee","year":"2002","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01553881","article-title":"Constrained delaunay triangulations","volume":"4","author":"Chew","year":"1989","journal-title":"Algorithmica"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1137\/0913058","article-title":"An O(n2\/log n) Time Algorithm for the Minmax Angle Triangulation","volume":"13","author":"Edelsbrunner","year":"1992","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Jain, A.K., and Law, M.H. (2005). Data clustering: A user\u2019s dilemma. International Conference on Pattern Recognition and Machine Intelligence, Springer.","DOI":"10.1007\/11590316_1"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.patcog.2007.04.010","article-title":"Robust path-based spectral clustering","volume":"41","author":"Chang","year":"2008","journal-title":"Pattern Recognit."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/1217299.1217303","article-title":"Clustering aggregation","volume":"1","author":"Gionis","year":"2007","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.1177\/0278364913491297","article-title":"Vision meets robotics: The KITTI dataset","volume":"32","author":"Geiger","year":"2013","journal-title":"Int. J. Robot. Res."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Douillard, B., Underwood, J., Kuntz, N., Vlaskine, V., Quadros, A., Morton, P., and Frenkel, A. (2011, January 9\u201313). On the segmentation of 3D LIDAR point clouds. Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China.","DOI":"10.1109\/ICRA.2011.5979818"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","article-title":"Maximum likelihood from incomplete data via the EM algorithm","volume":"39","author":"Dempster","year":"1977","journal-title":"J. R. Stat. Soc. Ser. B (Methodol.)"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1002\/(SICI)1097-0266(199606)17:6<441::AID-SMJ819>3.0.CO;2-G","article-title":"The application of cluster analysis in strategic management research: An analysis and critique","volume":"17","author":"Ketchen","year":"1996","journal-title":"Strateg. Manag. J."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Nurunnabi, A., Belton, D., and West, G. (2012, January 3\u20135). Robust segmentation in laser scanning 3D point cloud data. Proceedings of the 2012 International Conference on Digital Image Computing Techniques and Applications (DICTA), Fremantle, Australia.","DOI":"10.1109\/DICTA.2012.6411672"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Zhang, X., Xu, W., Dong, C., and Dolan, J.M. (2017, January 11\u201314). Efficient L-shape fitting for vehicle detection using laser scanners. Proceedings of the 2017 IEEE Intelligent Vehicles Symposium (IV), Los Angeles, CA, USA.","DOI":"10.1109\/IVS.2017.7995698"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/18\/3926\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:19:10Z","timestamp":1760188750000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/18\/3926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,12]]},"references-count":39,"journal-issue":{"issue":"18","published-online":{"date-parts":[[2019,9]]}},"alternative-id":["s19183926"],"URL":"https:\/\/doi.org\/10.3390\/s19183926","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,12]]}}}