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.
|
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). To Appear in Journal of Optimization Theory and Applications. [ PDF ]
|
|
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
|
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) Symposium on Computational Geometry 2003. [ gzipped PS ] [ Latest Version PDF ] [More details]
|
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]
|
|
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
|
|
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.
|
|
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 ]
|
|
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 ]
|
|
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 ]
|
|
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 ]
|