Yi-Jen Chiang

Associate Professor of Computer Science

How to Reach Me

yjc@poly.edu

Dept. of Computer Science and Engineering

Polytechnic Institute of NYU

2 MetroTech Center, 10th Floor

Brooklyn, NY 11201

USA

+1 (718) 260-3395 (office)

+1 (718) 260-3609 (fax)

Research Interests

Computer Algorithms: out-of-core algorithms, computational geometry, graph algorithms, approximation algorithms, data structures, computational topology.

Teaching

CS6043: Design and Analysis of Algorithms II (every spring semester from Spring 2000 to Spring 2007, and every semester since Spring 2008; latest: Spring 2013)

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 Program Committee Member

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


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

• ``On Soft Predicates in Subdivision Motion Planning,'' (conference version)
  C. Wang, Y.-J. Chiang and C. Yap.
  Conference version to appear in Proc. ACM Symp. Computational Geometry (SoCG '13), 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), 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 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: 4/12/2013