4 Result(s)
within
Kasturi R. Varadarajan
-
Article
Practical Methods for Shape Fitting and Kinetic Data Structures using Coresets
The notion of ε-kernel was introduced by Agarwal et al. (J. ACM 51:606–635, 2004) to set up a unified framework for computing various extent measures of a point set P approximately. Roughly speaking, a subset Q⊆
-
Article
Approximation Algorithms for a k-Line Center
Given a set P of n points in ℝd and an integer k ≥ 1, let w* denote the minimum value so that P can be covered by k congruent cylinders of radius w*. We describe a randomized algorithm that, given P and an ε > ...
-
Article
High-Dimensional Shape Fitting in Linear Time
Let $P$ be a set of $n$ points in $\Re^d$. The {\em radius} of a $k$-dimensional flat ${\cal F}$ with respect to $P$, which we denote by ${\cal RD}({\cal F},P)$, is defined to be $\max_{p \...
-
Chapter and Conference Paper
Approximation Algorithms for k-Line Center
Given a set P of n points in ℝd and an integer k ≥ 1, let w* denote the minimum value so that P can be covered by k cylinders of radius at most w*. We describe an algorithm that, given P and an ɛ > 0, computes k ...
