Combinatorial Geometry

In this research we concentrate on combinatorial aspects of geometric algorithms. Geometric algorithms dwell on geometric structures whose combinatorial complexity plays a major role in analysing the algorithms. We made some significant progress on one of the major problems in this area called k-sets. The upper bound on planar k-sets was improved to O(nk^1/3) from the previous known bound of O(nk^1/2/log^*n). The technique has since been used in many other results in the area.

Computational/Combinatorial Geometry 

  • B. Aronov and T. K. Dey. Polytopes in Arrangements . Discrete & Computational Geometry, Vol. 25, (2001), 51--63.
  • T. K. Dey. Improved bounds for planar k-sets and related problems. Invited paper in a special issue of Discrete & Computational Geometry, Vol. 19, No. 3, (1998), 373-382. Preliminary version in 37th IEEE FOCS, 1997, 156-161. 
  • T. K. Dey and J. Pach. Extremal problems for geometric hypergraphs. Discrete & Computational Geometry, Vol. 19, No. 4, (1998), 473--484. Preliminary version in ISAAC 96, LNCS 1178, 105-114. 
  • T. K. Dey and N. Shah. On counting the number of simplicial complexes in $R^d$. Computational Geometry: Theory and Applications Vol. 8, No. 5, (1997). Preliminary version in 7th CCCG, 1995, 31-36. 
  • T. K. Dey and H. Edelsbrunner. Counting triangle crossings and halving planes. Invited paper in a special issue, Discrete & Computational Geometry, Vol. 12 (1994), 281--289. 
  • T. K. Dey and N. Shah. Many face complexity in incremental convex arrangements. Information Processing Letters. Vol. 51, 5, 227--231 (1994). 
  • T. K. Dey. On counting triangulations in d dimensions. Computational Geometry: Theory and Applications. Vol. 3 (1993), 315--325. 
  • C. Bajaj and T. K. Dey. Polygon nesting and robustness. Information Processing Letters. Vol. 1 (1990), 23-32. 
  • D. Chithraprasad, S. P. Pal and T. K. Dey. Visibility with multiple diffuse reflections . Computational Geometry:Theory and Applications, Vol. 10, (1998), 187--196. 
  • B. Aronov, A. Davis, T. K. Dey, S. P. Pal and D. C. Prasad. Visibility with multiple reflections . Discrete & Computational Geometry, Vol. 20, No. 61, (1998), 61--78. Preliminary version in 5th SWAT, 1996, LNCS 1097, 284-295. 
  • B. Aronov, A. Davis, T. K. Dey, S. P. Pal and D. C. Prasad. Visibility with one reflection. Discrete & Computational Geometry, Vol. 19, No. 4, (1998), 553-574. Preliminary version in 11th ACM SoCG, 1995, 316-325. 


  • S. W. Cheng, T. K. Dey, H. Edelsbrunner, M. A. Facello and S.-H. Teng. Sliver exudation. Proc. 15th Sympos. Computational Geometry. 1999, 1--13. 
  • S. W. Cheng and T. K. Dey. Approximate minimum weight Steiner triangulation in three dimensions . Proc. 10th ACM-SIAM Symposium on Discrete Algorithms , (1999). 
  • T. K. Dey, A. Roy and N. R. Shah. Approximating geometric objects through topological triangulations. Proc. 17th. FST&TCS Conference, Lecture Notes in Computer Science 1346, 6-21 (1997). 
  • T. K. Dey, M. Dillencourt, S. Ghosh and J. Cahil. Triangulating with high connectivity. Computational Geometry: Theory and Applications, Vol. 8, No. 1, (1997), 39--56. Preliminary version in 6th CCCG, 1994, 339-343. 
  • T. K. Dey, C. Bajaj and K. Sugihara. On good triangulations in three dimensions. Intl. Journal of Computational Geometry & Applications. Vol. 2 (1992), 75-95. 
  • T. K. Dey, C. Bajaj and K. Sugihara. Delaunay triangulations in three dimensions with finite precision arithmetic. Computer Aided Geometric Design, Vol. 9 (1992), 457-470.