scheng


	Siu-Wing Cheng Professor Department of Computer Science and Engineering HKUST, Clear Water Bay Hong Kong Email: scheng@cse.ust.hk Tel: 852 23586973 Fax: 852 23581477

I enjoy doing research in algorithms, data structures, and computational geometry. Some of the research topics that I have worked on include point location, approximate shortest paths, mesh generation, and reconstruction of surfaces and manifolds, and shape matching. I have written a book, Delaunay Mesh Generation, with Tamal Dey and Jonathan Shewchuk. It is a thorough guide to Delaunay triangulation and mesh generation by Delaunay refinement.

ISAAC, Dec 16-19, 2018
The 29th International Symposium on Algorithms and Computation

Point Cloud Denoising for Surface Reconstruction
Executable and manuscript
Source code

Selected Professional Activities (full list)

ACM Distinguished Member for scientific contributions to computing.
Editorial board member of Computational Geometry: Theory and Applications.
Associate editor of International Journal of Computational Geometry and Applications.
Editorial board member of Journal of Computational Geometry.
Program co-chair of the 30th Annual Symposium on Computational Geometry, June 8-11, 2014, Kyoto, Japan.
Program co-chair of the 24th International Symposium on Algorithms and Computation, December 16-18, 2014, Hong Kong.
Some recent PC membership: SoCG18, SODA16, SWAT14, SoCG14, ISAAC13, WADS13, SoCG13, ISAAC12, ICALP12.
Advisory committee member of the International Symposium on Algorithms and Computation (ISAAC).
Chair of the Asian Association for Algorithms and Computation (AAAC).

Selected University Service

Associate Dean (Undergraduate Studies) of the School of Engineering, HKUST, January 2016 - present.
Acting Head of the Department of Computer Science and Engineering, HKUST, August 2013 - December 2014.
Associate Head of the Department of Computer Science and Engineering, HKUST, September 2007 - August 2011.
Chair of the University Scholarship Committee, HKUST, September 2010 - December 2014.
Chair of the CSE Substantiation and Promotion Committee, HKUST, July 2011 - June 2013.

Selected Publications (full list)

Point Location

Siu-Wing Cheng and Man-Kit Lau. Adaptive Planar Point Location. Proceedings of the International Conference on Computational Geometry (SOCG), 2017, 30:1-15.

Siu-Wing Cheng and Man-Kit Lau. Adaptive Point Location in Planar Convex Subdivisions. International Journal of Computational Geometry and Applications, 27 (2017), 3-12, special issue for the Proceedings of the 26th Internatinoal Symposium on Algorithms and Computation (ISAAC), 2015.

Siu-Wing Cheng and Ravi Janardan. New Results on Dynamic Planar Point Location. SIAM Journal on Computing, 21 (1992), 972-999.

Approximate Shortest Paths

Siu-Wing Cheng, Man-Kwun Chiu, Jiongxin Jin, and Antoine Vigneron. Navigating Weighted Regions with Scattered Skinny Tetrahedra. International Journal of Computational Geometry and Applications, 27 (2017), 13-32, special issue for Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), 2015.

Siu-Wing Cheng, Jiongxin Jin, and Antoine Vigneron. Triangulation Refinement and Approximate Shortest Paths in Weighted Regions. Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 2015, 1626-1640.

Siu-Wing Cheng and Jiongxin Jin. Shortest Paths on Polyhedral Surfaces and Terrains. Proceedings of the 46th Annual ACM Sympoisum on Theory of Computing, 2014, 373-382.

Siu-Wing Cheng and Jiongxin Jin.  Approximate Shortest Descending Paths. SIAM Journal on Computing, 43 (2014), 410-428.

Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron, and Yajun Wang.  Approximate Shortest Homotopic Paths in Weighted Regions. International Journal of Computational Geometry and Applications, 22 (2012), 83-102.

Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang.  Querying Approximate Shortest Paths in Anisotropic Regions. SIAM Journal on Computing, 39 (2010), 1888-1918.

Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang.  Approximate Shortest Paths in Anisotropic Regions. SIAM Journal on Computing, 38 (2008), 802-824.

Mesh Generation

Siu-Wing Cheng and Jionxin Jin.  Edge Flips in Surface Meshes. Discrete and Computational Geometry, 54 (2015), 110-151.

Siu-Wing Cheng and Jiongxin Jin. Deforming Surface Meshes. New Challenges in Grid Generation and Adaptivity for Scientific Computing, SEMA SIMAI Springer Series 5, edited by Simona Perotto and Luca Formaggia, pages 69-90, 2015.

Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos.  Delaunay Refinement for Piecewise Smooth Complexes. Discrete and Computational Geometry, 43 (2010), 121-166.

Siu-Wing Cheng, Tamal K. Dey, and Joshua A. Levine.  A Practical Delaunay Meshing Algorithm for a Large Class of Domains. Proceedings of the 16th International Meshing Roundtable, 2007, 477-494.

Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Tathagata Ray.  Sampling and Meshing a Surface with Guaranteed Topology and Geometry. SIAM Journal on Computing, 37 (2007), 1199-1227.

Siu-Wing Cheng and Sheung-Hung Poon.  Three-Dimensional Delaunay Mesh Generation. Discrete and Computational Geometry, 36 (2006), 419-456.

Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Raphael Wenger. Anisotropic Surface Meshing. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, 202-211.

Siu-Wing Cheng, Tamal K. Dey, and Tathagata Ray.  Weighted Delaunay Refinement for Polyhedra with Small Angles. Proceedings of the 14th International Meshing Roundtable, 2005, 323-342.

Siu-Wing Cheng and Tamal K. Dey. Quality Meshing with Weighted Delaunay Refinement. SIAM Journal on Computing, 33 (2003), 69-93.

Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng.   Sliver Exudation. Journal of the Association for Computer Machinery, 47 (2000), 883-904.

Reconstruction of Surfaces and Manifolds

Siu-Wing Cheng and Man-Kit Lau. Denoising a Point Cloud for Surface Reconstruction.   arXiv:1704.04028.   Missing images from the paper in the archive can be found here. The code can be downloaded from the project page.

Siu-Wing Cheng, Jiongxin Jin, and Man-Kit Lau.  A Fast and Simple Surface Reconstruction Algorithm. ACM Transactions on Algorithms, volume 13, issue 2, March 2017, article no. 27.

Siu-Wing Cheng and Man-Kwun Chiu. Tangent Estimation from Point Samples. Discrete and Computational Geometry, 56 (2016), 505-557.

Siu-Wing Cheng and Man-Kwun Chiu. Implicit Manifold Reconstruction. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 2014, 161-173.

Siu-Wing Cheng and Man-Kwun Chiu.  Dimension Detection via Slivers. Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, 1001-1010.

Siu-Wing Cheng, Yajun Wang, and Zhuangzhi Wu.  Provable Dimension Detection using Principal Component Analysis. International Journal of Computational Geometry and Applications, 18 (2008), 415-440.

Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos.  Manifold Reconstruction from Point Samples. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, 1018-1027.

Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-Hung Poon, and Edgar A. Ramos.  Curve Reconstruction from Noisy Samples. Computational Geometry: Theory and Applications, 31 (2005), 63-100 (Special issue of SoCG 2003).

Shape Matching

Juyoung Yon, Siu-Wing Cheng, Otfried Cheong, and Antoine Vigneron. Finding Largest Common Point Sets. International Journal of Computational Geometry and Applications, 27 (2017), 177-185.

Juyoung Yon, Sang Won Bae, Siu-Wing Cheng, Otfried Cheong, and Bryan T. Wilkinson. Approximating Convex Shapes with respect to Symmetric Difference under Homotheties. Proceedings of the International Symposium on Computational Geometry (SOCG), 2016, 63:1-15..

Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung Yon.  Overlap of Convex Polytopes under Rigid Motion, Computational Geometry: Theory and Applications, 47 (2014), 15-24.

Siu-Wing Cheng and Chi-Kit Lam.  Shape Matching under Rigid Motion. Computational Geometry: Theory and Applications, 46 (2013), 591-603.

Hee-Kap Ahn, Siu-Wing Cheng, and Iris Reinbacher.  Maximum Overlap of Convex Polytopes under Translation. Computational Geometry: Theory and Applications, 46 (2013), 552-565.

Other Topics

Siu-Wing Cheng and Yuchen Mao. Restricted Max-Min Fair Allocation. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018.

Siu-Wing Cheng, Yuya Higashikawa, Naoki Katoh, and Adnan Slijoka. Characterizing Minimal Rigidity of Square-Grid Frameworks with Holes. Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017, 93-102.

Siu-Wing Cheng, Liam Mencel, and Antoine Vigneron. A Faster Algorithm for Computing Straight Skeletons. ACM Transactions on Algorithms, volume 12, issue 3, article 44, May, 2016.

Ge Luo, Ke Yi, Siu-Wing Cheng, Zhenguo Li, Wei Fan, Cheng He, and Yadong Mu. Piecewise Linear Approximation of Streaming Time Series Data with Max-error Guarantees. Proceedings of the 31st IEEE International Conference on Data Engineering, 2015, 173-184.

Yuya Higashikawa, John Augustine, Siu-Wing Cheng, Mordecai J. Golin, Naoki Katoh, Guanqun Ni, Bing Su, and Yinfeng Xu.  Minimax Regret 1-Sink Location Problem in Dynamic Path Networks. Theoretical Computer Science, 588 (2015), 24-36.

Pankaj K. Agarwal, Siu-Wing Cheng, and Ke Yi.  Range Searching on Uncertain Data. ACM Transactions on Algorithms, 8 (2012), Article 43, 17 pages.

Siu-Wing Cheng and Antoine Vigneron.  Motorcycle Graphs and Straight Skeletons. Algorithmica, 47 (2007), 159-182.