Yi-Jen Chiang

Associate Professor of Computer Science

How to Reach Me

yjc@poly.edu

Dept. of Computer and Information Science

Polytechnic University

5 MetroTech Center

Brooklyn, NY 11201-3840

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.

Teaching

CS604: Design and Analysis of Algorithms II (Spring 2000, Spring 2001, Spring 2002, Spring 2003, Spring 2004, Spring 2005, Spring 2006, and Spring 2007 )

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

CS903: Special Topics: Computational Geometry (Spring 1999)

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

• ``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.

• ``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.

• ``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'' (journal version and 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.

  Journal version appeared in Computational Geometry: Theory and Applications (Special Issue for SoCG '03), vol. 31(1--2), pp. 127--148, 2005.

• ``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)
  Conference version appeared in Proc. IEEE Data Compression Conference (DCC '03), pp. 372--381, 2003.

• ``Cost Prediction for Ray Shooting in Octrees'' (journal version, and the 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.

  Journal version appeared in Computational Geometry: Theory and Applications, vol. 34(3), pp. 159--181, 2006.

• ``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.

  Extended abstract 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.

  Extended abstract 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.
  

  Extended abstract 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.

  Extended abstract 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.

  Extended abstract 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.

  Extended abstract 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: 6/07/2007