"...look into my eyes and repeat after me: I will cite your work at every possible opportunity..."

PAPERS


    JOURNALS

  1. An Optimal Generalization of the Centerpoint Theorem . ( Saurabh Ray).
    Computational Geometry: Theory and Applications , 2008.
  2. Weak eps-nets have a Basis of size O(1/eps log 1/eps) . ( Saurabh Ray).
    Computational Geometry: Theory and Applications , vol. 40(1), pp. 84-91, 2008.
  3. Fast Molecular Shape Matching Using Contact Maps . ( Pankaj Agarwal, Yusu Wang).
    Journal of Computational Biology, vol. 14(2), pp. 131-143, 2007.
  4. Statistical Data Depth and the Graphics Hardware . (Shankar Krishnan, Suresh Venkatasubramanian).
    Book Chapter in Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 223--250, 2006.
  5. Independent Set of Intersection Graphs of Convex Objects in 2D . ( Pankaj Agarwal).
    Computational Geometry: Theory and Applications, vol. 34(2), pp. 83-95, 2006.
  6. Dynamic Simplification and Visualization of Large Maps . (Shankar Krishnan, Gokul Varadhan, Suresh Venkatasubramanian).
    International Journal of Geographical Information Science, vol. 20(3), pp. 273-302, 2006.
  7. Near-Linear Time Approximation Algorithms for Curve Simplification. (Pankaj Agarwal, Sariel Har-Peled, Yusu Wang).
    Algorithmica, vol. 42(3), pp. 203-219, 2005.
  8. On a Conjecture of Wiener Indices in Combinatorial Chemistry . (Sergei Bespamyatnikh, Andrew Ban).
    Algorithmica, vol. 40(2), pp. 99-118, 2004.
  9. Listen to Your Neighbors: How (Not) to Reach a Consensus . (Aleksandar Pekec)
    SIAM Journal on Discrete Mathematics, vol. 17(4), pp. 634-660, 2004.

    REFEREED CONFERENCES

  10. Weak eps-nets have a Basis of size O(1/eps log 1/eps). (Saurabh Ray).
    Proc. of the 23rd ACM Symposium on Computational Geometry (SoCG '07), 2007.
  11. An Optimal Generalization of the Centerpoint Theorem. (Saurabh Ray).
    Proc. of the 23rd ACM Symposium on Computational Geometry (SoCG '07), 2007.
  12. Conflict-Free Colorings of Rectangle Ranges . ( Khaled Elbassioni ).
    Proc. of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS '06), 2006.
  13. Approximation Algorithms for Euclidean Group TSP . ( Khaled Elbassioni , Alex Fishkin , Rene Sitters ).
    Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP '05), 2005.
  14. Independent Set of Intersection Graphs of Convex Objects in 2D . ( Pankaj Agarwal ).
    Proc. of the 7th Scandinavian Workshop on Algorithm Theory (SWAT '04), 2004.
  15. k-Means Projective Clustering . ( Pankaj Agarwal ).
    Proc. of the 23rd Symposium on Principles of Database Systems (PODS '04), 2004.
  16. Streaming Geometric Optimization Using Graphics Hardware . ( Pankaj Agarwal, Shankar Krishnan, Suresh Venkatasubramanian).
    Proc. of the 11th European Symposium on Algorithms (ESA '03), 2003.
  17. On a Conjecture on Wiener Indices in Combinatorial Chemistry . (Sergei Bespamyatnikh, Andrew Ban).
    Proc. of the 9th International Computing and Combinatorics Conference '03 , 2003.
  18. Near-Linear Time Approximation Algorithms for Curve Simplification in Two and Three dimensions . (Pankaj Agarwal, Sariel Har-Peled, Yusu Wang).
    Proc. of the 10th European Symposium on Algorithms (ESA '02), 2002.
  19. Hardware Assisted Depth Contours. (Shankar Krishnan, Suresh Venkatasubramanian).
    Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), 2002.
  20. Hardware Assisted View-Dependent Planar Map Simplification. (Shankar Krishnan, Suresh Venkatasubramanian).
    Proc. of the 17th ACM Symposium on Computational Geometry (SoCG '01), 2001.
  21. Majority Consensus and the Local Majority Rule. (Aleksandar Pekec)
    Proc. of the 28th International Colloquium on Automata, Languages and Programming (ICALP '01), 2001.


OTHER


    EXPOSITIONS

  1. Slides on the point-line incidences problem.
    Slides on constructing optimal cuttings using the Chazelle-Friedman sample-and-repair technique, Crossing Lemma proofs, and their use for point-line incidences problem. I tried to make the cutting construction as simple, clean and intuitive as possible, so that the later work of Clarkson-Varadarajan etc. is much simpler to understand.
  2. Slides on Entropy.
    Slides on entropy, from a combinatorial point of view. How the entropy definition etc. falls out from the binomial bounds, and the use of entropy in Shannon's error-correcting theorem.

    NON-TECHNICAL ARTICLES

  3. On Being Smart.
    This article was written for the LUMS undergraduate student magazine. I try to make the case that succeeding in graduate school is almost completely determined by hard-work, as opposed to genius. Old story, and not much new to add.


SOFTWARE

I plan to put up the source code of the missing software online soon. I have yet to properly comment and package each piece of code put below. In the meanwhile, you'll have to do with this.


  1. MapSimp: Hardware-Assisted Planar Map Simplification. SGI, IRIX 64.
    Software for computing planar map simplifications efficiently using the graphics hardware. Also allows real-time navigation of the map, with heirarchical levels of detail simplification. Previously, no such real-time dynamic fast map simplification algorithm existed. Algorithm for the dynamic map simplification described in my paper "Hardware Assisted View-Dependent Planar Map Simplification". Download MapSimp binary.
  2. DepthCont: Hardware-Assisted Computation of Depth Contours. SGI, IRIX 64.
    Software for fast computation of planar depth contours using the predicates allowed by the graphics hardware. Outperforms the previous best-known algorithms by orders of magnitude. Algorithm described in my paper "Hardware-Assisted Computation of Depth Contours". Download DepthCont .
  3. CurveSimp: Approximate Curve Simplification. SunOS.
    Software for approximating a piece-wise linear curve with fewer vertices. Implements the factor-2 approximation algorithm from my paper "Near-Linear time algorithms for Curve Simplification". Download SimpCurve.
  4. FindIndex: Find Index Representation. SunOS.
    This is the code-snippet for finding appropriate representation of any integer n as the Wiener index of the computed tree. The program outputs a 4-tuple that encodes (implicitly) the tree whose Wiener index is n. Implements the matrix-searching algorithm as described in my paper "On a Conjecture of Wiener Indices in Combinatorial Chemistry". Download FindIndex.