My Research Papers [BibTex]


A Core Set Result for the Weighted Euclidean One-Center Problem..
Given A = { a1,..., am } ⊂ Rn with corresponding positive weights W = { w1,..., wm}, the weighted Euclidean one-center problem, which is a generalization of the minimum enclosing ball problem, involves the computation of a point cA that minimizes the maximum weighted Euclidean distance from cA to each point in A. In this paper, given ε > 0, we propose and analyze an algorithm that computes a (1 + ε)-approximate solution to the weighted Euclidean one-center problem. The approximation algorithm outputs a core-set for the problem as well. We also implement our algorithm and show implementation results.

(Joint work with Alper Yildirim).
(Submitted) Available at Optimization Online.

Computing Minimum Volume Enclosing Axis-Aligned Ellipsoids..
Given a set of points S = { x1,..., xm } ⊂ Rn and ε>0, we propose and analyze an algorithm for the problem of computing a (1+ε)-approximation to the the minimum volume axis-aligned ellipsoid enclosing S. We establish that our algorithm is polynomial for fixed ε. In addition, the algorithm returns a small core set X ⊆ S, whose size is independent of the number of points m, with the property that the minimum volume axis-aligned ellipsoid enclosing X is a good approximation of the minimum volume axis-aligned ellipsoid enclosing S. Our computational results indicate that the algorithm exhibits significantly better performance than that indicated by the theoretical worst-case complexity result.

(Joint work with Alper Yildirim).
Journal of Optimization Theory and Applications 136 (2) pp. 211-228 (2008). [ DOI ] [ PDF ].
Also Presented at : Euro-OMS, Euro XXII: [PPT]

Finding Large Sticks and Potatoes in Polygons.
We study a class of optimization problems in polygons that seeks to compute the largest subset of a prescribed type, e.g., a longest line segment (stick) or a maximum-area triangle or convex body (potato). Exact polynomial-time algorithms are known for some of these problems, but their time bounds are high (e.g., O(n7) for the largest convex polygon in a simple n-gon). We devise efficient approximation algorithms for these problems. In particular, we give near-linear time algorithms for a (1-ε)-approximation of the biggest stick, a constant factor approximation of the maximum-area convex body, and a (1-ε)-approximation of the maximum-area fat triangle or rectangle. In addition, we give efficient methods for computing large ellipses inside a polygon (whose vertices are a dense sampling of closed smooth curve). Our algorithms include both deterministic and randomized methods, one of which has been implemented (for computing large area ellipses in a well sampled closed smooth curve).

(Joint work with Olaf Hall-Holt, Matya Katz, Joe Mitchell and Arik Sityon).
In Proceedings of SODA 2006. [ Paper: PDF ] [Implementation] [SODA Talk: PPT PDF ]

Approximate Minimum Volume Enclosing Ellipsoids Using Core Sets.
In this paper we study the problem of computing the minimum volume enclosing ellipsoid containing a given point set . Using ``core sets'' and a column generation approach, we develop a -approximation algorithm. We prove the existence of a core set of size at most . We describe an algorithm that computes the set and a -approximation to the minimum volume enclosing ellipsoid of in operations by using Khachiyan's algorithm to solve each subproblem. This result is an improvement over the previously known algorithms especially for input sets with and reasonably small values of . We also discuss extensions to the cases in which the input set consists of balls or ellipsoids.

Invited talks at: [ Informs ] [ Workshop on Geometric Optimization ]
(Joint work with Alper Yildirim).
Journal of Optimization Theory and Applications 126 (Vol 1) pp. 1-21 (July 2005). [ PDF ]

I/O Efficient Construction of Voronoi diagrams.
We develop here a cache oblivious voronoi diagram and delaunay triangulation algorithm. We also develop and implement a simpler divide and conquer based out of core algorithm to do delaunay triangulations in 2D.

(Joint work with Edgar Ramos)
Coming Up

Curve Reconstruction from Noisy Samples.
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation in the normal directions. Our reconstruction is faithful with probability at least , where is the number of noisy samples and is the maximum local feature size. We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.

(Joint work with Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Sheung-Hung Poon and Edgar Ramos)
Preliminary version appeared in Proceedings of Symposium on Computational Geometry 2003.

Invited to/Accepted in special issue of Computational Geometry - Theory and Applications (CGTA), Vol. 31, Issue 1-2, May 2005, p. 63-100.

[ gzipped PS ] [ Latest Version PDF ] [More details]

Fast smallest enclosing hypersphere computation.
We study the minimum enclosing ball (MEB) problem for sets of points or balls in high dimensions. Using techniques of second-order cone programming and ``core-sets'', we have developed -approximation algorithms that perform well in practice, especially for very high dimensions, in addition to having provable guarantees. We prove the existence of core-sets of size , improving the previous bound of , and we study empirically how the core-set size grows with dimension. We show that our algorithm, which is simple to implement, results in fast computation of nearly optimal solutions for point sets in much higher dimension than previously computable using exact techniques.

(Joint work with Joe Mitchell and Alper Yildirim).

Proceedings of Alenex 2003, pages 45-55. [ PDF ] [ Alenex Talk PDF ]
Also Presented at: [ Euro Informs ] [ Workshop on Geometric Optimization ]
Invited to/Accepted in Special issue of Journal of Experimental Algorithmics [Journal Version PDF] [Alenex Version PDF]
[More details of the implementation]

Cache Oblivious Algorithms.
The cache oblivious model is a simple and elegant model to design algorithms that perform well in hierarchical memory models ubiquitous on current systems. This model was first formulated in FLPR99 and has since been a topic of intense research. Analyzing and designing algorithms and data structures in this model involves not only an asymptotic analysis of the number of steps executed in terms of the input size, but also the movement of data optimally among the different levels of the memory hierarchy. This chapter is aimed as an introduction to the ``ideal-cache'' model of FLPR99 and techniques used to design cache oblivious algorithms. The chapter also presents some experimental insights and results.

[Chapter Webpage] © Springer-Verlag 2003
Springer Verlag's Chapter Page.
Algorithms for Memory Hierarchies, LNCS 2625, pages 193-212, Springer Verlag.

Associated Talk: Cache Oblivious Algorithms: Theory and Practice

Hand recognition using geometric classifiers.
We discuss the issues and challenges in the design of a hand outline based recognition system. Our system is easier to use, cheaper to build and more accurate than previous systems. Extensive tests on more than 700 images collected from 70 people are reported. Classification, verification and identification of the input images were done using two simple geometric classifiers. We describe a novel minimum enclosing ball classifier which performs well for hand recognition and could be of interest for other applications. The paper uses tricks from a broad range of areas including computational geometry, image processing, optimization and machine learning.

(Joint work with Yaroslav Bulatov, Saurabh Sethia, Sachin Jambawalikar)
Fall Workshop on Computational Geometry 2002. [ PS ] [ PPT Slides ]
[ GRC 2003 ] Best Paper Award in its Category
To Appear in Proceedings of International Conference on Biometric Authentication 2004.

Reviver: A Practical Provable Surface Reconstructor.
Given a set of points from a smooth surface, how do we create the connections to generate a manifold in 3D? We give a practical provable algorithm to do so.
Fall Workshop on Computational Geometry 2001. [ PDF ]

[ Reviver Web Page ]
I also maintain a page on Surface reconstruction [ Link ]

A Simple Provable Algorithm for Curve Reconstruction.
Given a set of points from a smooth curve, we show using a simple algorithm how to create the connections.
(Joint Work with T. K. Dey)
Appeared in Symposium on Discrete Algorithms 99. [ PDF ] [ PS ]

A simple polygon triangulation algorithm.
We developed an algorithm that can triangulate a polygon in near linear time when I was visiting Tata Institute of Fundamental Research, Bombay in Summer of 99. Our Algorithm is currently based on the shape complexity(k) of the input polygon and runs in O(nlogk). For instance, k = 1 for the polygon drawn on the left.
(Joint work with Dr. Subir Ghosh)
Technical Report. [ PDF ]


Simplifying Polygonal Approximations of 2D Shapes.
Given a polygonal curve approximating a smooth shape, we show using a simple algorithm how to simplify it.
Was accepted in Shape Modelling 99. [ PS ]

My B.Sc. Project Report(An Extension of the above paper). [ PS Version ]

Ph.D. Thesis
Clustering and Reconstructing Large Data Sets
.
This thesis deals with problems at the intersection of computational geometry, optimization, graphics, and machine learning. Geometric clustering is one such problem we explore. We develop fast approximation algorithms for clustering problems like the k-center problem and minimum enclosing ellipsoid problem based on the idea of core sets. We also explore an application of the 1-center problem to recognition of people based on their hand outlines.

Another problem we consider in this thesis is how to reconstruct curves and surfaces from given sample points. We show implementations of algorithms that can handle noise for reconstructing curves in two dimensions. Based on Delaunay triangulations, we develop a surface reconstructor for a given set of sample points in three dimensions.

When dealing with massive data sets, it is important to consider the effect of memory hierarchies on algorithms. We explore this problem in our research on cache oblivious algorithms. We develop a practical cache oblivious algorithm to compute Delaunay triangulations of large point sets. We end the thesis with another optimization problem of approximately finding large empty convex bodies inside closed objects under various assumptions.

Thesis: Download PDF Version here [8.9Mb]
[ My first Job Talk :) ] [6.6Mb] (May 2004)


Other Writeups
My Published Reviews (ACM Computing Reviews) 




Lecture Notes/Hand outs of Classes 

My Talk Slides

Surface Reconstruction

Alpha Shapes

Well Separated Pair Decomposition

Cache Oblivious Algorithms: Theory and Practice
(Based on Harold Prokop's Slides).

Core Sets for Minimum Enclosing Balls

Perceptrons [ SVM ]

More coming soon...:)

Back to my homepage
Created on Mon, December 22, 1997.