Yi-Jen Chiang

Associate Professor of Computer Science

How to Reach Me

chiang@nyu.edu

Dept. of Computer Science and Engineering

Tandon School of Engineering

New York University

370 Jay Street, 11th Floor

Brooklyn, NY 11201

USA

+1 (646) 997-3395 (office)

+1 (646) 997-3609 (fax)

Research Interests

Computer Algorithms: out-of-core algorithms; computational geometry; algorithmic motion planning; graph algorithms; approximation algorithms; data structures; computational topology.

Teaching

CS6033: Design and Analysis of Algorithms I (Fall 2015, Fall 2017, Spring 2019, Spring and Fall 2020, Fall 2021, Fall 2022, and Fall 2023)

CS6043: Design and Analysis of Algorithms II (every spring semester from Spring 2000 to Spring 2007, and every semester from Spring 2008 to Fall 2014; Spring 2016, and Fall 2019)

CS1122: Introduction to Computer Science (Spring 2020)

CS6005, CS6010, CS6015, CS6020, CS6025: Guided Studies in Computer Science: Graduate Projects (Fall 2007)

CS394: Special Topics in Computer Science: Senior Projects (Fall 2004, Fall 2005, and Fall 2006)

CS903: Special Topics: Computational Geometry (Spring 1999)

Recent Papers Co-Chair and Program Committee Member

Papers Co-Chair, IS&T Visualization and Data Analysis (VDA), 2024


Papers Co-Chair, IS&T Visualization and Data Analysis (VDA), 2023


Papers Co-Chair, IS&T Visualization and Data Analysis (VDA), 2022


Papers Co-Chair, IS&T Visualization and Data Analysis (VDA), 2021


Papers Co-Chair, IS&T Visualization and Data Analysis (VDA), 2020


Papers Co-Chair, IS&T Visualization and Data Analysis (VDA), 2019


Papers Co-Chair, IS&T Visualization and Data Analysis (VDA), 2018


Area Co-Chair (for the Visualization area), International Symposium on Visual Computing (ISVC), 2011


PC Member, IEEE Visualization Conference (VIS), 2024


PC Member, International Symposium on Visual Computing (ISVC), 2024


PC Member, IEEE Visualization Conference (VIS), 2023


PC Member, International Symposium on Visual Computing (ISVC), 2023


PC Member, IEEE/Eurographics Conference on Visualization (EuroVis), 2022


PC Member, International Symposium on Visual Computing (ISVC), 2022


PC Member, IEEE/Eurographics Conference on Visualization (EuroVis), 2021


PC Member, International Symposium on Visual Computing (ISVC), 2021


PC Member, IEEE/Eurographics Conference on Visualization (EuroVis), 2020


PC Member, International Symposium on Visual Computing (ISVC), 2020


PC Member, International Symposium on Visual Computing (ISVC), 2019


PC Member, International Symposium on Visual Computing (ISVC), 2018


PC Member, IEEE/Eurographics Conference on Visualization (EuroVis), 2017


PC Member, IS&T Visualization and Data Analysis (VDA), 2017


PC Member, IEEE/Eurographics Conference on Visualization (EuroVis), 2016


PC Member, International Symposium on Visual Computing (ISVC), 2016


PC Member, IS&T Visualization and Data Analysis (VDA), 2016


PC Member, IEEE/Eurographics Conference on Visualization (EuroVis), 2015 (for both Full Papers and Short Papers)


PC Member, International Symposium on Visual Computing (ISVC), 2015


PC Member, SPIE Visualization and Data Analysis (VDA), 2015


PC Member, IEEE/Eurographics Conference on Visualization (EuroVis), 2014


PC Member, International Symposium on Visual Computing (ISVC), 2014


PC Member, SPIE Visualization and Data Analysis (VDA), 2014


PC Member, International Symposium on Visual Computing (ISVC), 2013


PC Member, SPIE Visualization and Data Analysis (VDA), 2013


PC Member, IEEE/Eurographics Conference on Visualization (EuroVis), 2012


PC Member, International Symposium on Visual Computing (ISVC), 2012


PC Member, SPIE Visualization and Data Analysis (VDA), 2012


PC Member, Eurographics (EG) 2011 Posters


PC Member, IEEE Visualization Conference (Vis), 2010


PC Member, International Symposium on Visual Computing (ISVC), 2010


PC Member, International Conference on Information Visualization Theory and Applications (IVAPP), 2010


PC Member, IEEE Visualization Conference (Vis), 2009


PC Member, International Symposium on Visual Computing (ISVC), 2009


PC Member, IEEE Visualization Conference (Vis), 2008


PC Member, International Symposium on Visual Computing (ISVC), 2008

Tutorial Courses

• ``Out-of-Core Algorithms for Scientific Visualization and Computer Graphics,''
  C.T. Silva, Y.-J. Chiang, J. El-Sana, and P. Lindstrom.
  IEEE Visualization Conference 2002, Boston, MA, 2002.

---

Datasets

Papers

Computer Graphics and Visualization

• ``Optimal Path Planning on a Semi-Dynamic Subdivision Graph,''
  Y.-J. Chiang, D. Kirkpatrick, C. Yap, and Z. Zhang.
  International Workshop on Search and Planning with Complex Objectives (WoSePCO '23), 2023. Workshop affiliated to IJCAI 2023.
  

• ``Streaming Approach to In Situ Selection of Key Time Steps for Time-Varying Volume Data''
  (separate web page, including full paper, talk slides and code)
  M. Wu, Y.-J. Chiang, and C. Musco.
  Journal version appeared in Computer Graphics Forum (Special Issue for Eurographics/IEEE Conference on Visualization (EuroVis '22)), vol. 41(3), pp. 309--320, 2022.
  

• ``Soft Subdivision Motion Planning for Complex Planar Robots,'' (journal version)
  B. Zhou, Y.-J. Chiang and C. Yap.
  Journal version appeared in Computational Geometry: Theory and Applications (CGTA), volume 92, 101683, 2021.
  Link to the Gallery of Video Clips
  The ultimate journal version from the publisher is available at
  https://www.sciencedirect.com/science/article/pii/S0925772120300778
  (Conference version and the talk slides are available here. )
  

• ``Efficient Local Statistical Analysis via Point-Wise Histograms in Tetrahedral Meshes and Curvilinear Grids,'' (journal version)
  B. Zhou, Y.-J. Chiang and C. Wang.
  IEEE Transactions on Visualization and Computer Graphics (TVCG), vol. 25(2), pp. 1392--1406, 2019.
  (Presented at IEEE VIS (SciVis) 2018. )
  Supplementary Materials: Appendices and Additional Images
  IEEE VIS (SciVis) Talk Slides in PDF
  

• ``Rods and Rings: Soft Subdivision Planner for R^3 x S^2,'' (conference version)
  C.-H. Hsu, Y.-J. Chiang and C. Yap.
  Conference version appeared in Proc. Symposium on Computational Geometry (SoCG '19), pp. 43:1--43:17, 2019.
  Link to the Gallery of Video Clips
  SoCG Talk Slides in PDF
  Full version of the paper (also hosted on arXiv as arXiv:1903.09416 [cs.CG], containing all proofs and some additional background in the appendices).
  

• ``Key Time Steps Selection for Large-Scale Time-Varying Volume Datasets Using an Information-Theoretic Storyboard,'' (journal version)
  B. Zhou and Y.-J. Chiang.
  Journal version appeared in Computer Graphics Forum (Special Issue for Eurographics/IEEE Conference on Visualization (EuroVis '18)), vol. 37(3), pp. 37--49, 2018.
  Supplementary Material 1: Appendices and Additional Images
  Supplementary Material 2: Video Clip
  EuroVis Talk Slides in PDF (detailed version)
  

• ``Soft Subdivision Motion Planning for Complex Planar Robots,'' (conference version)
  B. Zhou, Y.-J. Chiang and C. Yap.
  Conference version appeared in Proc. European Symposium on Algorithms (ESA '18), pp. 73:1--73:14, 2018.
  Link to the Gallery of Video Clips
  ESA Talk Slides in PDF
  An earlier full version of the paper (also hosted on arXiv as arXiv:1906.06154 [cs.CG], containing all proofs, new Fig. 7, typo fixed in Eq. (6), new comments between Eq. (6) and Lemma 4, a new paragraph right after Theorem 6, and new Table 1).
  (Journal version is available here. )
  

• ``Soft Subdivision Planner for a Rod,''
  C.-H. Hsu, Y.-J. Chiang and C. Yap.
  Fall Workshop on Computational Geometry (FWCG '16), October 27-28, 2016.
  

• ``On Soft Predicates in Subdivision Motion Planning,'' (journal version)
  C. Wang, Y.-J. Chiang and C. Yap.
  Journal version appeared in Computational Geometry: Theory and Applications (CGTA), Special Issue for SoCG '13, vol. 48(8), pp. 589--605, 2015.
  (This was one of the best five papers selected from SoCG '13 and invited for this special issue.)
  The ultimate journal version from the publisher is available at
  http://authors.elsevier.com/a/1R5ui3IVmU3hlO
  for free download until July 16, 2015.
  

• ``Resolution-Exact Algorithms for Link Robots,'' (conference version)
  Z. Luo, Y.-J. Chiang, J.-M. Lien and C. Yap.
  Conference version appeared in Proc. Intl. Workshop on the Algorithmic Foundations of Robotics (WAFR '14), pp. 353--370, 2014.
  Also appeared in Springer Tracts in Advanced Robotics (STAR) volume 107, Springer, 2015 (ISBN 978-3-319-16594-3).
  Link to the Gallery of Video Clips
  

  Full version (including two additional Appendices) is available.
  

• ``On Soft Predicates in Subdivision Motion Planning,'' (conference version)
  C. Wang, Y.-J. Chiang and C. Yap.
  Conference version appeared in Proc. ACM Symp. Computational Geometry (SoCG '13), pp. 349--358, 2013.
  

• ``Scalable Computation of Distributions from Large Scale Data Sets,'' (conference version)
  A. Chaudhuri, T.-Y. Lee, B. Zhou, C. Wang, T. Xu, H.-W. Shen, T. Peterka, and Y.-J. Chiang.
  Conference version appeared in Proc. IEEE Symp. Large Scale Data Analysis and Visualization (LDAV '12), pp. 113--120, 2012.
  

• ``Numerical Subdivision Methods in Motion Planning,''
  Y.-J. Chiang and C. Yap.
  IROS 2011 Workshop on Progress and Open Problems in Motion Planning, 2011.
  [This is a lightly edited version of the IROS version]
  

• ``Out-of-Core Simplification and Crack-Free LOD Volume Rendering for Irregular Grids,'' (journal version)
  Z. Du and Y.-J. Chiang.
  Journal version appeared in Computer Graphics Forum (Special Issue for Eurographics/IEEE Symposium on Visualization (EuroVis '10)), vol. 29(3), pp. 873--882, 2010.
  Supplementary Material 1: Appendices and Additional Images
  Supplementary Material 2: Video Clip
  Talk Slides in PDF (detailed version)
  

• ``Isosurface Extraction and View-Dependent Filtering from Time-Varying Fields Using Persistent Time-Octree (PTOT),'' (journal, correct version)
  C. Wang and Y.-J. Chiang.
  Journal version appeared in IEEE Transactions on Visualization and Computer Graphics (Special Issue for IEEE Visualization Conference (Vis '09)), vol. 15(6), pp. 1367--1374, 2009.
  Remark: In both the printed and the digital-library versions, in Figures 1--4, all occurrences of ``-'' between words and all occurrences of space between words are gone. The correct version is provided above.
  Supplementary Material: Video Clip
  Talk Slides in PDF

• ``Out-of-Core Volume Rendering for Time-Varying Fields Using a Space-Partitioning Time (SPT) Tree,'' (conference version)
  Z. Du, Y.-J. Chiang, and H.-W. Shen.
  Conference version appeared in Proc. IEEE Pacific Visualization Symposium (PacificVis '09), pp. 73--80, 2009.
  Technical Report (same as the conference version, with additional materials in Sections 3.3.1, 3.3.2 and Appendix)
  

• ``Out-of-Core Progressive Lossless Compression and Selective Decompression of Large Triangle Meshes,'' (conference version)
  Z. Du, P. Jaromersky, Y.-J. Chiang, and N. Memon.
  Conference version appeared in Proc. IEEE Data Compression Conference (DCC '09), pp. 420--429, 2009.
  

• ``Alphabet Partitioning Techniques for Semi-Adaptive Huffman Coding of Large Alphabets'' (journal version),
  D. Chen, Y.-J. Chiang, N. Memon, and X. Wu.
  Journal version appeared in IEEE Transactions on Communications, vol. 55(3), pp. 436--443, 2007.
  Technical Report (same as the journal version, with additional materials in Section 4.1 and Appendix A)
  

• ``Lossless Geometry Compression for Steady-State and Time-Varying Irregular Grids,'' (conference version)
  D. Chen, Y.-J. Chiang, N. Memon and X. Wu.
  Conference version appeared in Proc. Eurographics/IEEE Symposium on Visualization (EuroVis '06), pp. 275--282, May, 2006.
  EuroVis '06 Talk Slides in .pdf
  ``Lossless Geometry Compression for Floating-Point Data in Steady-State and Time-Varying Fields over Irregular Grids,'' (full version) Revised May 2007.
  Submitted for a journal publication.

• ``Cost Prediction for Ray Shooting in Octrees'' (journal version),
  B. Aronov, H. Bronnimann, A.Y. Chang and Y.-J. Chiang.
  Journal version appeared in Computational Geometry: Theory and Applications, vol. 34(3), pp. 159--181, 2006.

• ``Lossless Compression of Point-Based 3D Models,'' (conference version)
  D. Chen, Y.-J. Chiang, and N. Memon.
  Conference version appeared in Proc. Pacific Graphics (PG '05), pp. 124--126, 2005.

• ``Geometry Compression of Tetrahedral Meshes Using Optimized Prediction,'' (conference version)
  D. Chen, Y.-J. Chiang, N. Memon, and X. Wu.
  Conference version appeared in Proc. European Conference on Signal Processing (EUSIPCO '05), 2005.

• ``Optimized Prediction for Geometry Compression of Triangle Meshes,'' (conference version)
  D. Chen, Y.-J. Chiang, N. Memon, and X. Wu.
  Conference version appeared in Proc. IEEE Data Compression Conference (DCC '05), pp. 83--92, 2005.
  Talk slides in .pdf (one slide per page) and (four slides per page)

• ``Simple and Optimal Output-Sensitive Construction of Contour Trees Using Monotone Paths'' (journal version)
  Y.-J. Chiang, T. Lenz, X. Lu and G. Rote.
  Journal version appeared in Computational Geometry: Theory and Applications (Special Issue for EuroCG '03), vol. 30(2), pp. 165--195, 2005.

• ``Cost-Driven Octree Construction Schemes: An Experimental Study'' (journal version),
  B. Aronov, H. Bronnimann, A.Y. Chang and Y.-J. Chiang.
  Journal version appeared in Computational Geometry: Theory and Applications (Special Issue for SoCG '03), vol. 31(1--2), pp. 127--148, 2005.

• ``Multiple-Description Geometry Compression for Networked Interactive 3D Graphics,'' (conference version, and full version )
  P. Jaromersky, X. Wu, Y.-J. Chiang and N. Memon.
  Conference version appeared in Proc. IEEE International Conference on Image and Graphics (ICIG '04), pp. 468--471, 2004.

  Full version submitted for a journal publication.

• ``Out-of-Core Isosurface Extraction of Time-Varying Fields over Irregular Grids,'' (conference version)
  Y.-J. Chiang.
  Conference version appeared in Proc. IEEE Visualization '03 (Vis '03), pp. 217--224, 2003.

• ``Out-of-Core Algorithms for Scientific Visualization and Computer Graphics,''
  C.T. Silva, Y.-J. Chiang, J. El-Sana, and P. Lindstrom.
  Submitted for a journal publication.

• ``Progressive Simplification of Tetrahedral Meshes Preserving All Isosurface Topologies,''
  Y.-J. Chiang and X. Lu.
  Journal version appeared in Computer Graphics Forum, vol. 22(3), pp. 493--504, 2003 (Special Issue for Eurographics '03).
  Talk slides in .pdf

• ``Cost-Driven Octree Construction Schemes: An Experimental Study'' (conference version),
  B. Aronov, H. Bronnimann, A.Y. Chang and Y.-J. Chiang.
  Conference version appeared in Proc. ACM Symp. on Computational Geometry (SoCG '03), pp. 227--236, 2003.

• ``Optimal Alphabet Partitioning for Semi-Adaptive Coding of Sources of Unknown Sparse Distributions'' (conference version),
  D. Chen, Y.-J. Chiang, N. Memon, and X. Wu.
  Conference version appeared in Proc. IEEE Data Compression Conference (DCC '03), pp. 372--381, 2003.

• ``Cost Prediction for Ray Shooting'' (conference version)
  B. Aronov, H. Bronnimann, A.Y. Chang and Y.-J. Chiang.
  Conference version appeared in Proc. ACM Symp. on Computational Geometry (SoCG '02), pp. 293--302, 2002.

• ``A Unified Infrastructure for Parallel Out-Of-Core Isosurface Extraction and Volume Rendering of Unstructured Grids'' (conference version),
  Y.-J. Chiang, R. Farias, C.T. Silva, and B. Wei.
  Conference version appeared in Proc. IEEE Symposium on Parallel and Large-Data Visualization and Graphics 2001 (PVG '01), pp. 59--66, 2001.

• ``External Memory View-Dependent Simplification'' (separate web page)
  J. El-Sana and Y.-J. Chiang
  Journal version appeared in Computer Graphics Forum , vol. 19(3), pp. 139--150, August 2000 (Special Issue for Eurographics '00) as the winner of The Best Paper Award, Eurographics 2000.

• ``External Memory Techniques for Isosurface Extraction in Scientific Visualization'' (journal version),
  Y.-J. Chiang and C.T. Silva.
  Journal version appeared in External Memory Algorithms and Visualization, J. Abello and J.S. Vitter (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, vol. 50, pp. 247--277, 1999.

• ``Interactive Out-Of-Core Isosurface Extraction'' (conference version),
  Y.-J. Chiang, C.T. Silva and W.J. Schroeder.
  Conference version appeared in Proc. IEEE Visualization '98 (Vis'98), pp. 167--174, 1998.

• ``Isosurface Extraction in Large Scientific Visualization Applications Using the I/O-filter Technique'' (full paper),
  Y.-J. Chiang and C.T. Silva.
  

• ``I/O Optimal Isosurface Extraction'' (full version), and conference version.
  Y.-J. Chiang and C.T. Silva.
  Conference version appeared in Proc. IEEE Visualization '97 (Vis'97), pp. 293--300, 1997.

• ``Geometric Algorithms for Conflict Detection/Resolution in Air Traffic Management'' (conference version),
  Y.-J. Chiang, J.T. Klosowski, C. Lee, and J.S.B. Mitchell.
  Conference version appeared in Proc. 36th IEEE Conference on Decision and Control '97 (CDC '97), pp. 1835--1840, 1997.

• ``Experiments on the Practical I/O Efficiency of Geometric Algorithms: Distribution Sweep vs. Plane Sweep'' (journal version),
  Y.-J. Chiang.
  Computational Geometry: Theory and Applications. vol. 9(4), pp. 211--236, 1998.

  Conference version appeared in Proc. Workshop on Algorithms and Data Structures (WADS'95), Lecture Notes in Computer Science, vol. 955, pp. 346--357, 1995.
  

Computer Algorithms

• ``New Approximation Results for the Maximum Scatter TSP'' (journal version),
  Y.-J. Chiang.
  Journal version appeared in Algorithmica, vol. 41(4), pp. 309--341, 2005.

• ``Two-Point Euclidean Shortest Path Queries in the Plane'' (conference version),
  Y.-J. Chiang and J.S.B. Mitchell.
  Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA'99), pp. 215--224, 1999.

• ``On the Maximum Scatter TSP'' (journal version, contains more results than the conference version),
  E.M. Arkin, Y.-J. Chiang, J.S.B. Mitchell, S.S. Skiena, and T.-C. Yang.
  Journal version appeared in SIAM Journal on Computing, vol. 29(2), pp. 515--544, 1999.

  Conference version appeared in Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA'97), pp. 211--220, 1997.

• ``On Minimum-Area Hulls'' (journal version).
  E.M. Arkin, Y.-J. Chiang, M. Held, J.S.B. Mitchell, V. Sacristan, S.S. Skiena, and T.-C. Yang.
  Algorithmica, Special Issue for ESA'96, vol. 21, pp. 119--136, 1998.
  

  Conference version appeared in Proc. European Symp. on Algorithms (ESA'96), Lecture Notes in Computer Science, vol. 1136, pp. 334--348, 1996.
  

• ``External-Memory Graph Algorithms'' (conference version),
  Y.-J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff, and J.S. Vitter.
  Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA'95), pp. 139--149, 1995.

• ``Optimal Shortest Path and Minimum-Link Path Queries Between Two Convex Polygons Inside a Simple Polygonal Obstacle'' (journal version),
  Y.-J. Chiang and R. Tamassia.
  Int. J. of Computational Geometry & Applications, Special Issue, E.M.Arkin, J.S.B. Mitchell and S. Skiena (Ed.), vol. 7(1 & 2), pp. 85-121, 1997.

  Conference version appeared in Proc. European Symp. on Algorithms (ESA'94), Lecture Notes in Computer Science, vol. 855, pp. 266-277, 1994.
  

• ``A Unified Approach to Dynamic Point Location, Ray Shooting and Shortest Paths in Planar Maps''
  (journal version),
  Y.-J. Chiang, F.P. Preparata, and R. Tamassia.
  SIAM Journal on Computing, vol. 25(1), pp. 207--233, 1996.

  Conference version appeared in Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA'93), pp. 44-53, 1993.

• ``Dynamization of the Trapezoid Method for Planar Point Location in Monotone Subdivisions''
  (journal version),
  Y.-J. Chiang and R. Tamassia.
  Int. J. of Computational Geometry & Applications, Special Issue, D.T. Lee (Ed.), vol. 2(3), pp. 311-333, 1992.

  Conference version appeared in Proc. ACM Symp. on Computational Geometry (SoCG'91), pp. 61-70, 1991.

• ``Dynamic Algorithms in Computational Geometry'' (journal version),
  Y.-J. Chiang and R. Tamassia.
  Proceedings of the IEEE, Special Issue on Computational Geometry, G. Toussaint (Ed.), vol. 80(9),
  pp. 1412-1434, 1992.

---

Ph.D. Thesis: ``Dynamic and I/O-Efficient Algorithms for Computational Geometry and Graph Problems: Theoretical and Experimental Results'' (separate web page)

---

Last update: 3/12/2024