%0 Conference Paper
%B Proceedings of the twenty-fourth annual symposium on Computational geometry
%D 2008
%T Embedding and similarity search for point sets under translation
%A Cho,Minkyoung
%A Mount, Dave
%K EMBEDDING
%K point pattern matching
%K randomized algorithms
%K Similarity Search
%X Pattern matching in point sets is a well studied problem with numerous applications. We assume that the point sets may contain outliers (missing or spurious points) and are subject to an unknown translation. We define the distance between any two point sets to be the minimum size of their symmetric difference over all translations of one set relative to the other. We consider the problem in the context of similarity search. We assume that a large database of point sets is to be preprocessed so that given any query point set, the closest matches in the database can be computed efficiently. Our approach is based on showing that there is a randomized algorithm that computes a translation-invariant embedding of any point set of size at most n into the L_1 metric, so that with high probability, distances are subject to a distortion that is O(log2 n).
%B Proceedings of the twenty-fourth annual symposium on Computational geometry
%S SCG '08
%I ACM
%C New York, NY, USA
%P 320 - 327
%8 2008///
%@ 978-1-60558-071-5
%G eng
%U http://doi.acm.org/10.1145/1377676.1377731
%R 10.1145/1377676.1377731
%0 Journal Article
%J Information Processing Letters
%D 2008
%T A note on the distribution of the number of prime factors of the integers
%A Srinivasan, Aravind
%K Chernoff bounds
%K Dependent random variables
%K Primes
%K Probabilistic number theory
%K randomized algorithms
%K Tail bounds
%X The Chernoff–Hoeffding bounds are fundamental probabilistic tools. An elementary approach is presented to obtain a Chernoff-type upper-tail bound for the number of prime factors of a random integer in { 1 , 2 , … , n } . The method illustrates tail bounds in negatively-correlated settings.
%B Information Processing Letters
%V 109
%P 133 - 135
%8 2008/12/31/
%@ 0020-0190
%G eng
%U http://www.sciencedirect.com/science/article/pii/S0020019008002688
%N 2
%R 10.1016/j.ipl.2008.09.010
%0 Journal Article
%J Computational Statistics & Data Analysis
%D 2007
%T A practical approximation algorithm for the LMS line estimator
%A Mount, Dave
%A Netanyahu,Nathan S.
%A Romanik,Kathleen
%A Silverman,Ruth
%A Wu,Angela Y.
%K Approximation algorithms
%K least median-of-squares regression
%K line arrangements
%K line fitting
%K randomized algorithms
%K robust estimation
%X The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of n points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0 < q ⩽ 1 . This problem is equivalent to finding the strip defined by two parallel lines of minimum vertical separation that encloses at least half of the points.The best known exact algorithm for this problem runs in O ( n 2 ) time. We consider two types of approximations, a residual approximation, which approximates the vertical height of the strip to within a given error bound ε r ⩾ 0 , and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound ε q ⩾ 0 . We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and ε q > 0 runs in O ( n log n ) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm's expected running time is O ( n log 2 n ) . We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm.
%B Computational Statistics & Data Analysis
%V 51
%P 2461 - 2486
%8 2007/02/01/
%@ 0167-9473
%G eng
%U http://www.sciencedirect.com/science/article/pii/S0167947306002921
%N 5
%R 10.1016/j.csda.2006.08.033
%0 Journal Article
%J ACM Transactions on Algorithms (TALG)
%D 2007
%T A simple entropy-based algorithm for planar point location
%A Arya,Sunil
%A Malamatos,Theocharis
%A Mount, Dave
%K Entropy
%K expected-case complexity
%K Point location
%K polygonal subdivision
%K randomized algorithms
%K trapezoidal maps
%X Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability pz that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. In this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in O(H) average time. We also present empirical evidence for the practical efficiency of this approach.
%B ACM Transactions on Algorithms (TALG)
%V 3
%8 2007/05//
%@ 1549-6325
%G eng
%U http://doi.acm.org/10.1145/1240233.1240240
%N 2
%R 10.1145/1240233.1240240
%0 Journal Article
%J Computational Geometry
%D 2001
%T Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses
%A Mount, Dave
%A Netanyahu,Nathan S.
%K Aligned ellipse fitting
%K Arrangements
%K Circular arc fitting
%K computational geometry
%K randomized algorithms
%K Range searching
%K RM estimator
%K robust estimation
%K Theil–Sen estimator
%X Fitting two-dimensional conic sections (e.g., circular and elliptical arcs) to a finite collection of points in the plane is an important problem in statistical estimation and has significant industrial applications. Recently there has been a great deal of interest in robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50%) of outlying data points that can corrupt the estimator. In this paper we introduce nonlinear Theil–Sen and repeated median (RM) variants for estimating the center and radius of a circular arc, and for estimating the center and horizontal and vertical radii of an axis-aligned ellipse. The circular arc estimators have breakdown points of ≈ 21% and 50%, respectively, and the ellipse estimators have breakdown points of ≈ 16% and 50%, respectively. We present randomized algorithms for these estimators, whose expected running times are O(n2logn) for the circular case and O(n3logn) for the elliptical case. All algorithms use O(n) space in the worst case.
%B Computational Geometry
%V 19
%P 1 - 33
%8 2001/06//
%@ 0925-7721
%G eng
%U http://www.sciencedirect.com/science/article/pii/S0925772101000098
%N 1
%R 10.1016/S0925-7721(01)00009-8
%0 Conference Paper
%B Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures
%D 2001
%T Finding large independent sets of hypergraphs in parallel
%A Shachnai,Hadas
%A Srinivasan, Aravind
%K hypergraphs
%K independent sets
%K Parallel algorithms
%K randomized algorithms
%X A basic problem in hypergraphs is that of finding a large independent set-one of guaranteed size-in a given hypergraph. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a fundamental open issue in parallel computation. Caro and Tuza (J. Graph Theory, Vol. 15, pp. 99-107, 1991) have shown a certain lower bound &agr;k(H) on the size of a maximum independent set in a given k-uniform hypergraph H, and have also presented an efficien sequential algorithm to find an independent set of size &agr;k (H). They also show that &agr;k (H) is the size of the maximum independent set for various hypergraph families. Here, we develop the first RNC algorithm to find an independent set of size &agr;k(H), and also derandomize it for various special cases. We also present lower bounds on independent set size and corresponding RNC algorithms for non-uniform hypergraphs.
%B Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures
%S SPAA '01
%I ACM
%C New York, NY, USA
%P 163 - 168
%8 2001///
%@ 1-58113-409-6
%G eng
%U http://doi.acm.org/10.1145/378580.378622
%R 10.1145/378580.378622
%0 Journal Article
%J Mathematics of Operations ResearchMathematics of Operations Research
%D 2000
%T Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
%A Baveja,Alok
%A Srinivasan, Aravind
%K Approximation algorithms
%K Disjoint paths
%K integer programming
%K Linear programming
%K multicommodity flow
%K Packing
%K randomized algorithms
%K rounding
%K Routing
%K unsplittable flow
%X Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered; the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented.
%B Mathematics of Operations ResearchMathematics of Operations Research
%V 25
%P 255 - 280
%8 2000/05/01/
%@ 0364-765X, 1526-5471
%G eng
%U http://mor.journal.informs.org/content/25/2/255
%N 2
%R 10.1287/moor.25.2.255.12228
%0 Conference Paper
%B Proceedings of the twenty-ninth annual ACM symposium on Theory of computing
%D 1997
%T A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria
%A Srinivasan, Aravind
%A Teo,Chung-Piaw
%K Approximation algorithms
%K covering integer programs
%K discrete ham-sandwich theorems
%K Linear programming
%K packet routing
%K randomized algorithms
%K Randomized rounding
%K rounding theorems
%B Proceedings of the twenty-ninth annual ACM symposium on Theory of computing
%S STOC '97
%I ACM
%C New York, NY, USA
%P 636 - 643
%8 1997///
%@ 0-89791-888-6
%G eng
%U http://doi.acm.org/10.1145/258533.258658
%R 10.1145/258533.258658
%0 Conference Paper
%B Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms
%D 1997
%T A practical approximation algorithm for the LMS line estimator
%A Mount, Dave
%A Netanyahu,Nathan S.
%A Romanik,Kathleen
%A Silverman,Ruth
%A Wu,Angela Y.
%K Approximation algorithms
%K least median-of-squares regression
%K line arrangements
%K line fitting
%K randomized algorithms
%K robust estimation
%B Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms
%S SODA '97
%I Society for Industrial and Applied Mathematics
%C Philadelphia, PA, USA
%P 473 - 482
%8 1997///
%@ 0-89871-390-0
%G eng
%U http://dl.acm.org/citation.cfm?id=314161.314349
%0 Conference Paper
%B Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
%D 1994
%T Randomized and deterministic algorithms for geometric spanners of small diameter
%A Arya,S.
%A Mount, Dave
%A Smid,M.
%K computational geometry
%K deletions
%K deterministic algorithms
%K directed graph
%K directed graphs
%K geometric spanners
%K insertions
%K randomised algorithms
%K randomized algorithms
%X Let S be a set of n points in IR^{d} and let t gt;1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and p. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. Randomized and deterministic algorithms are given for constructing t-spanners consisting of O(n) edges and having O(log n) diameter. Also, it is shown how to maintain the randomized t-spanner under random insertions and deletions. Previously, no results were known for spanners with low spanner diameter and for maintaining spanners under insertions and deletions
%B Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
%P 703 - 712
%8 1994/11//
%G eng
%R 10.1109/SFCS.1994.365722