|
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.
[PDF] (Joint work with Alper Yildirim). (Accepted to Informs Journal on Computing, 2009) Available at Optimization Online.
|
We present a parallel algorithm for k-nearest neighbor
graph construction
that uses Morton ordering.
Experiments show that our approach has the following advantages
over existing methods:
(To appear in Point Based Graphics 2008). Software available at STANN's website.
|
|
Given a set of points P and a query point q, the
reverse furthest neighbor (RFN) query fetches the set of points
p ε P such that q is their furthest neighbor among all points in
P union q. This is the monochromatic RFN (MRFN) query. Another
interesting version of RFN query is the bichromatic reverse furthest
neighbor (BRFN) query. Given a set of points P, a query set
Q and a query point q ε Q, a BRFN query fetches the set
of points p ε P such that q is the furthest neighbor of p
among all points in Q. The RFN query has many interesting
applications in spatial databases and beyond. For instance, given
a large residential database (as P) and a set of potential sites
(as Q) for building a chemical plant complex, the construction
site should be selected as the one that has the maximum number
of reverse furthest neighbors. This is an instance of the BRFN
query. This paper presents the challenges associated with such
queries and proposes efficient, R-tree based algorithms for both
monochromatic and bichromatic versions of the RFN queries.
[PDF] (Joint work with Bin Yao and Feifei Li).
|
|
This paper presents a method for finding large empty convex bodies
within a 3D scene of polygonal models. The convex bodies we pack are
discrete orientation polytopes (k-dops) with a small number of
facets. The algorithm searches for a large empty k-dop within the
scene, using a combination of random sampling and physical simulation,
allowing the body to grow and interact (via rotation, translation, and
scaling) with the environment when collisions are detected.
We pack multiple empty k-dops in a 3D scene using a greedy
incremental approach, attempting to maximize the volume of each new
body found. We demonstrate the practicality of our method
experimentally, showing that it is fast and that it does
an effective job of packing on a variety of models.
[PDF] (Joint work with Uday Chebrolu and Joe Mitchell). Selected papers of the Sixth International Conference on Computational Science and Applications (ICCSA), IEEE CS, Perugia, Italy. Pages: 382-393, June 2008.
|
|
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 the problem of computing
the Minimum Volume Enclosing Ellipsoid (MVEE) containing
a given set of ellipsoids S =
{E1,E2,...,En }⊂ Rd.
We show how to efficiently compute a small set
X ⊆ S of size at most
|X| = O(d2 / ε)
whose minimum volume ellipsoid is an (1+ε)-approximation
to the minimum volume ellipsoid of S. We use an augmented real
number model of computation to achieve a running time of
O(|X|ndω+d3) where
ω < 2.376 is the exponent of matrix multiplication.
This is the best known complexity for solving the MVEE problem when n
is much larger than d, and ε is large.
The algorithm is built on the
previous work by Kumar and Yildirim.
[PDF] (Joint work with Sachin Jambawalikar). Selected papers of the Sixth International Conference on Computational Science and Applications (ICCSA), IEEE CS, Perugia, Italy. Pages: 478-490, June 2008. (To appear in ICCSA 2008)
|
|
We use projective clustering to design and implement a fast surface
reconstruction algorithm for point clouds that also works well for
sharp edges and corners. Our method relies on
two new approximation algorithms developed and implemented for the
first time, namely, fast projective clustering and parallel dynamic nearest
neighbor searching based on shifted quad-trees. Also, our implementation
is one of the first for this problem with
any kind of guarantees (for a
very restricted type of manifolds). Our algorithm
is easy to parallelize and is external-memory friendly. Finally
we provide a method for combining increasingly more complex fitters in
a cascade which allows planar regions of the point
cloud to be quickly processed while spending more time on high
curvature areas including sharp features. In the domain
of normal estimation, our method is faster and more accurate than
previous systems on a large number of point clouds.
(Joint work with Amit Mhatre) Proceedings of the twenty-second annual symposium on Computational geometry, Sedona, Arizona, USA, 2006. Multimedia abstracts. Pages: 477 - 478. Preliminary version appeared in Fall workshop on Computational Geometry. [ Paper: PDF ]
|
|
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 ]
|
