|
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.
|
|
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]
|
|
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 ]
|
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 ]
|
|
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) 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]
|
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 ]
|
|
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 ]
|
