Home
|
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.
Visibility
-
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.
Triangulations
-
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.
|