ABSTRACT On the Importance of Idempotence (2008)
Range searching is among the most fundamental problems in computational geometry. An n-element point set in R d is given along with an assignment of weights to these points from some commutative...
Given a set of IR ¢ points in, called sites, we consider the problem of approximating the ¡ Voronoi cell £ of a site by a convex polyhedron with a small number of facets or, equivalently, of...
Abstract. 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...
Sunil Arya, Siu-wing Cheng, David M. Mount
Received received date Revised revised date Communicated by Editor’s name Milling is the mechanical process of removing material from a piece of stock through the use of a rapidly spinning circular...
Interactive tools for morphometry in video (2008)
Daniel Dementhon, Sunil Arya, Larry S. Davis, Jacob Glaser, Edmund Glaser
microscopy
Efficient Construction of a Bounded Degree Spanner (2008)
Low Weight, Sunil Arya, Michiel Smid
Let S be a set of n points in IR d and let t> 1 be a real number. A t-spanner for S is a graph having the points of S as its vertices such that for any pair p,q of points there is a path between...
ABSTRACT On the Importance of Idempotence (2008)
Range searching is among the most fundamental problems in computational geometry. An n-element point set in R d is given along with an assignment of weights to these points from some commutative...
Binary space partitions for axis-parallel line segments: size-height tradeoffs (2008)
We present worst-case lower bounds on the minimum size of a binary space partition (BSP) tree as a function of its height, for a set S of n axis-parallel line segments in the plane. We assume that...
Sunil Arya, Siu-wing Cheng, David M. Mount, H. Ramesh
Abstract. Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time,...
Interactive Tools for Morphometry in Video Microscopy (2007)
Daniel Dementhon, Sunil Arya, Larry S. Davis, Jacob Glaser, Edmund Glaser
We describe algorithms for measuring the thickness of neuron processes and the shape of neuron cell bodies. The design of these tools follows a "semi-automatic" approach. Image processing...
Sunil Arya, David M. Mount, Nathan S. Netanyahu, Angela Y. Wu
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct...
Abstract A Simple Entropy-Based Algorithm for Planar Point Location (2007)
Sunil Arya, Theocharis Malamatos, David M. Mount
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...
Sunil Arya, David M. Mount, Michiel Smid
Randomized and deterministic algorithms for geometric spanners of small diameter
Binary space partitions for axis-parallel line segments: size-height tradeoffs (2007)
We present worst-case lower bounds on the minimum size of a binary space partition (BSP) tree as a function of its height, for a set S of n axis-parallel line segments in the plane. We assume that...
Abstract. We consider a restricted version of the general Set Covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the Set...
Abstract. We consider a restricted version of the general Set Covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the Set...
Sunil Arya, David M. Mount, Michiel Smid
Randomized and deterministic algorithms for geometric spanners of small diameter
Entropy-Preserving Cuttings and Space-Ecient (2007)
Planar Point Location, Sunil Arya, Theocharis Malamatos, David M. Mount
Point location is the problem of preprocessing a planar polygonal subdivision S into a data structure in order to determine e#ciently the cell of the subdivision that contains a given query point....
Approximating a Voronoi Cell (2007)
called sites, we consider the problem of approximating the Voronoi cell of a site p by a convex polyhedron with a small number of facets or, equivalently, of finding a small set of approximate...
Optimal expected-case planar point location (2007)
Arya, Sunil, Malamatos, Theocharis, Mount, David M., Wong, Ka Chun
Space-Time Tradeoffs for Approximate Spherical Range Counting (2006)
Arya, Sunil, Malamatos, Theocharis, Mount, David M.
We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in real d-dimensional space along with a positive approximation factor eps, the goal...
Space-Time Tradeoffs for Approximate Spherical Range Counting (2006)
Arya, Sunil, Malamatos, Theocharis, Mount, David M.
We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in real d-dimensional space along with a positive approximation factor eps, the goal...
On the importance of idempotence (2006)
Sunil Arya, Theocharis Malamatos, David M. Mount
Answering range queries is a problem of fundamental importance in spatial information retrieval and computational geometry. The objective is to store a set of n points P in R d, each associated with...
The effect of corners on the complexity of approximate range searching (2006)
Range searching is among the most fundamental problems in computational geometry. Given an n-element point set in R d, the problem is to preprocess the points so that the total weight (or generally...
The effect of corners on the complexity of approximate range searching (2006)
Sunil Arya, Theocharis Malamatos, David M. Mount
Given an n-element point set in R d, the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a...
The Effect of Corners on the Complexity of Approximate Range Searching (2006)
Arya, Sunil, Malamatos, Theocharis, Mount, David M., Amenta, Nina, Cheong, Otfried
Space-time tradeoffs for approximate spherical range counting (2005)
Sunil Arya, Theocharis Malamatos, David M. Mount
Abstract We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in Rdalong with a positive approximation factor ffl, the goal is to...
Space-time tradeoffs for approximate spherical range counting (2005)
Sunil Arya, Theocharis Malamatos, David M. Mount
We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in R d along with a positive approximation factor ɛ, the goal is to preprocess the...
Space-time tradeoffs for approximate spherical range counting (2005)
Sunil Arya, Theocharis Malamatos, David M. Mount
We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in R d along with a positive approximation factor ǫ, the goal is to preprocess the...
A simple entropy-based algorithm for planar point location (2004)
Arya, Sunil, Malamatos, Theocharis, Mount, David M.
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...
Expected-Case complexity of approximate nearest neighbor searching (2003)
Most research in algorithms for geometric query problems has focused on their worst-case performance. But when information on the query distribution is available, the alternative paradigm of...
Approximating a voronoi cell (2003)
Arya, Sunil, Vigneron, Antoine
Given a set S of n points in IRd, called sites, we consider the problem of approximating the Voronoi cell of a site p by a convex polyhedron with a small number of facets or, equivalently, of finding...
Approximate range searching (2002)
The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show...
Linear-Size Approximate Voronoi Diagrams (2002)
Sunil Arya, Theocharis Malamatos
a (t; ffl)-approximate Voronoi diagram (AVD) is a partition of space into constant complexity cells, where each cell c is associated with t representative points of S, such that for any point in c,...
Space-efficient approximate Voronoi diagrams (2002)
Given a set S of n points in IR d, a (t, ǫ)-approximate Voronoi diagram (AVD) is a partition of space into constant complexity cells, where each cell c is associated with t representative points of...
Space-Efficient Approximate Voronoi Diagrams (2002)
Sunil Arya, Theocharis Malamatos, David M. Mount
a(t, #)-approximate Voronoi diagram (AVD) is a partition of space into constant complexity cells, where each cell c is associated with t representative points of S, such that for any point in c, one...
Space-Efficient Approximate Voronoi Diagrams (2002)
Sunil Arya, Theocharis Malamatos, David M. Mount
a (t; ffl)-approximate Voronoi diagram (AVD) is a partition of space into constant complexity cells, where each cell c is associated with t representative points of S, such that for any point in c,...
A simple entropy-based algorithm for planar point location (2001)
Sunil Arya, Theocharis Malamatos, David M. Mount
Abstract Given a planar polygonal subdivision S, point location involves preprocessing this subdivisioninto a data structure so that given any query point q, the cell of the subdivision containing...
A simple entropy-based algorithm for planar point location (2001)
Sunil Arya, Theocharis Malamatos, David M. Mount
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...
Entropy-preserving cuttings and space-efficient planar point location (2001)
Sunil Arya, Theocharis Malamatos, David M. Mount
Point location is the problem of preprocessing a planar polygonal subdivision S into a data structure in order to determine efficiently the cell of the subdivision that contains a given query point....
A simple entropy-based algorithm for planar point location (2001)
Sunil Arya, Theocharis Malamatos, David M. Mount
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...
A simple entropy-based algorithm for planar point location (2001)
Sunil Arya, Theocharis Malamatos, David M. Mount
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...
Efficient Expected-Case Algorithms for Planar Point Location (2000)
Arya, Sunil, Cheng, Siu-Wing, Mount, David M, Ramesh, H
Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time, there has...
Hardness of set cover with intersection 1 (2000)
Kumar, Anil VS, Arya, Sunil, Ramesh, H
We consider a restricted version of the general Set Covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the Set Covering...
Efficient Expected-Case Algorithms for Planar Point Location (2000)
Arya, Sunil, Cheng, Siu-Wing, Mount, David M, Ramesh, H
Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time, there has...
Hardness of set cover with intersection 1 (2000)
Kumar, Anil VS, Arya, Sunil, Ramesh, H
We consider a restricted version of the general Set Covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the Set Covering...
Nearly optimal expected-case planar point location (2000)
Sunil Arya, Theocharis Malamatos
We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that...
Expected-case complexity of approximate nearest neighbor searching (2000)
Most research in algorithms for geometric query problems has focused on their worstcase performance. But when information on the query distribution is available, the alternative paradigm of designing...
Nearly optimal expected-case planar point location (2000)
Sunil Arya, Theocharis Malamatos, David M. Mount
We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that...
Expected-Case Complexity of Approximate Nearest Neighbor Searching (2000)
Most research in algorithms for geometric query problems has focused on their worstcase performance. But when information on the query distribution is available, the alternative paradigm of designing...
Nearly Optimal Expected-Case Planar Point Location (2000)
Sunil Arya Theocharis, Sunil Arya, Theocharis Malamatos, David M. Mount
We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that...
Nearly optimal expected-case planar point location (2000)
Sunil Arya, Theocharis Malamatos, David M. Mount, Ka Chun Wong
Point location is the problem of preprocessing a planar polygonal subdivision S of size n into a data structure in order to determine efficiently the cell of the subdivision that contains a given...
Expected-case complexity of approximate nearest neighbor searching (2000)
Most research in algorithms for geometric query problems has focused on their worstcase performance. However, when information on the query distribution is available, the alternative paradigm of...
Nearly optimal expected-case planar point location (2000)
Sunil Arya, Theocharis Malamatos, David M. Mount, Ka Chun Wong
Abstract. Point location is the problem of preprocessing a planar polygonal subdivision S of size n into a data structure in order to determine efficiently the cell of the subdivision that contains a...
Efficient expected-case algorithms for planar point location (2000)
Sunil Arya, Siu-wing Cheng, David M. Mount, H. Ramesh
Abstract. Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time,...
Approximation algorithm for multiple-tool milling (1999)
Arya, Sunil, Cheng, Siu-Wing, Mount, David M.
Milling is the mechanical process of removing material from a piece of stock through the use of a rapidly spinning circular milling tool in order to form some desired geometric shape. An important...
Approximation Algorithm for Multiple-Tool Milling (1999)
Sunil Arya, Siu-Wing Cheng, David M. Mount
Milling is the mechanical process of removing material from a piece of stock through the use of a rapidly spinning circular milling tool in order to form some desired geometric shape. An important...
Dynamic algorithms for geometric spanners of small diameter: Randomized solutions (1999)
Sunil Arya, David M. Mount, Michiel Smid
Let S be a set of n points in IR d and let t> 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...
On the expected depth of random circuits (1999)
Sunil Arya, Mordecai J. Golin, Kurt Mehlhorn
Abstract: In this paper we analyze the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from...
On the Expected Depth of Random Circuits (1999)
Arya, Sunil, Golin, Mordecai J., Mehlhorn, Kurt
In this paper we analyse the expected depth of random circuits of fixed fanin f . Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the...
On the expected depth of random circuits (1998)
Arya, Sunil, Golin, Mordecai J., Mehlhorn, Kurt
In this paper we analyze the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the...
A 2.5-factor approximation algorithm for the k-MST problem (1998)
The k-MST problem requires finding that subset of at least k vertices of a given graph whose Minimum Spanning Tree has least weight amongst all subsets of at least k vertices, There has been much...
A 2.5-factor approximation algorithm for the k-MST problem (1998)
The k-MST problem requires finding that subset of k vertices of a given graph whose Minimum Spanning Tree has least weight amongst all subsets of k vertices. There has been much work on this problem...
Approximation Algorithms for Multiple-Tool Milling (1998)
Sunil Arya, Siu-Wing Cheng, David M. Mount
Milling is the mechanical process of removing material from a piece of stock through the use of a rapidly spinning circular milling tool in order to form some desired geometric shape. An important...
Approximation Algorithms for Multiple-Tool Milling (1998)
Sunil Arya, Siu-Wing Cheng, David M. Mount
Milling is the mechanical process of removing material from a piece of stock through the use of a rapidly spinning circular milling tool in order to form some desired geometric shape. An important...
On the Expected Depth of Random Circuits (1998)
Sunil Arya, Mordecai J. Golin, Kurt Mehlhorn
: In this paper we analyze the expected depth of random circuits of fixed fanin f: Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the...
A 2.5-factor approximation algorithm for the k-MST problem (1998)
The k-MST problem requires finding that subset of at least k vertices of a given graph whose Minimum Spanning Tree has least weight amongst all subsets of at least k vertices. There has been much...
A 2.5 Factor Approximation Algorithm for the k-MST Problem (1997)
The k-MST problem requires finding that subset of at least k vertices of a given graph whose Minimum Spanning Tree has least weight amongst all subsets of at least k vertices. There has been much...
ANN: A Library for Approximate Nearest Neighbor Searching (1997)
3.37> ffl There are no exponential factors in space, implying that the data structure is practical even for very large data sets in high dimensional spaces, irrespective of ffl. ANN is written as...
Accounting for Boundary Effects in Nearest Neighbor Searching (1996)
Sunil Arya, Searching Sunil, Arya David, David M. Mount, Onuttom Narayan
Given n data points in d-dimensional space, nearest neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest neighbor...
Nearest neighbor searching and applications /--by Sunil Arya. (1995)
Thesis research directed by Dept. of Computer Science.
Accounting for boundary effects in nearest neighbor searching (1995)
Sunil Arya, David M. Mount, Onuttom Narayan
x Given n data points in d-dimensional space, nearest neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest neighbor...
Approximate Range Searching (1995)
The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show...
Approximate Range Searching (1995)
The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show...
Euclidean Spanners: Short, Thin, and Lanky (1995)
Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, Michiel Smid
Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest...
Approximate Range Searching (1995)
The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show...
Accounting for Boundary Effects in Nearest Neighbor Searching (1995)
Sunil Arya, David M. Mount, Onuttom Narayan
Given n data points in d-dimensional space, nearest neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest neighbor...
Efficient Construction of a Bounded Degree Spanner with Low Weight (1995)
Let S be a set of n points in IR d and let t ? 1 be a real number. A t-spanner for S is a graph having the points of S as its vertices such that for any pair p; q of points there is a path between...
Euclidean Spanners: Short, Thin, and Lanky (1995)
Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, Michiel Smid
Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest...
Approximate range searching (1995)
The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show...
Accounting for boundary effects in nearest neighbor searching (1995)
Sunil Arya, David M. Mount, Onuttom Narayan
Given n data points in d-dimensional space, nearest neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest neighbor...
Approximate range searching (1995)
The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show...
Accounting for Boundary Effects in Nearest Neighbor Searching (1995)
Sunil Arya, David M. Mount, Onuttom Narayan
Given n data points in d-dimensional space, nearest neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest neighbor...
Dynamic algorithms for geometric spanners of small diameter: Randomized solutions (1994)
Sunil Arya, David M. Mount, Michiel Smid
Let S be a set of n points in IR d and let t ? 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...
An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions (1994)
Sunil Arya, David M. Mount, Nathan S. Netanyahu, Angela Y. Wu
Consider a set S of n data points in real d-dimensional space, R d , where distances are measured using any Minkowski metric. In nearest neighbor searching we preprocess S into a data structure, so...
Dynamic algorithms for geometric spanners of small diameter: Randomized solutions (1994)
Sunil Arya, David M. Mount, Michiel Smid
Let S be a set of n points in IR d and let t ? 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...
An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions (1994)
Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu
Consider a set S of n data points in real d-dimensional space, R d , where distances are measured using any Minkowski metric. In nearest neighbor searching we preprocess S into a data structure, so...
Dynamic algorithms for geometric spanners of small diameter: Randomized solutions (1994)
Sunil Arya, David M. Mount, Michiel Smid
Let S be a set of n points in IR d and let t ? 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...
Algorithms for fast vector quantization (1993)
Nearest neighbor searching is an important geometric subproblem in vector quantization. Existing studies have shown that the difficulty of solving this problem efficiently grows rapidly with...
Algorithms for Fast Vector Quantization (1993)
Nearest neighbor searching is an important geometric subproblem in vector quantization. Existing studies have shown that the difficulty of solving this problem efficiently grows rapidly with...
Approximate Nearest Neighbor Queries in Fixed Dimensions (1993)
Given a set of n points in d-dimensional Euclidean space, S ae E d , and a query point q 2 E d , we wish to determine the nearest neighbor of q, that is, the point of S whose Euclidean distance to q...
Algorithms for Fast Vector Quantization (1993)
Nearest neighbor searching is an important geometric subproblem in vector quantization. Existing studies have shown that the difficulty of solving this problem efficiently grows rapidly with...
Algorithms for fast vector quantization (1993)
Nearest neighbor searching is an important geometric subproblem in vector quantization. Existing studies have shown that the difficulty of solving this problem efficiently grows rapidly with...