## Recent Publications:

### Approximate Nearest Neighbor Searching and Polytope Approximation:

- R. Arya, S. Arya, G. D. da Fonseca, and D. M. Mount,
Optimal bound on the combinatorial complexity of approximating polytopes,
*Proc. 31st ACM-SIAM Symp. on Discrete Algorithms (SODA)*, 786-805, 2020. - A. Abdelkader, S. Arya, G. D. da Fonseca, and D. M. Mount,
Approximate nearest neighbor searching with non-Euclidean and weighted distances,
*Proc. 30th ACM-SIAM Symp. on Discrete Algorithms (SODA)*, 355-372, 2019. - S. Arya, G. D. da Fonseca, and D. M. Mount,
Approximate convex intersection detection with applications to width and Minkowski sums,
*Proc. 26th European Symp. on Algorithms (ESA)*, 3:1-3:14, 2018. - S. Arya, G. D. da Fonseca, and D. M. Mount,
Near-optimal epsilon-kernel construction and related problems,
*Proc. 33rd Internat. Symp. on Computational Geometry (SoCG)*, 10:1-15, 2017. - S. Arya, G. D. da Fonseca, and D. M. Mount,
Optimal approximate polytope membership,
*Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (SODA)*, 270-288, 2017. - S. Arya, G. D. da Fonseca, and D. M. Mount,
Approximate polytope membership queries,
*SIAM Journal on Computing*, 47(1):1-51, 2018. (Also, in STOC 2011 and SODA 2012.) - S. Arya, G. D. da Fonseca, and D. M. Mount,
On the combinatorial complexity of approximating polytopes,
*Discrete and Computational Geometry*, 58(4):849-870, 2017. (Also, in SoCG 2016.) - S. Arya and T. M. Chan,
Better epsilon-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and epsilon-kernels,
*Proc. 30th Symp. on Computational Geometry (SoCG)*, 416-425, 2014. - S. Arya, G. D. da Fonseca, and D. M. Mount,
Optimal area-sensitive bounds for polytope approximation,
*Proc. 28th Symp. on Computational Geometry (SoCG)*, 363-372, 2012. - S. Arya, G. D. da Fonseca, and D. M. Mount,
Polytope approximation and the Mahler volume,
*Proc. 23rd ACM-SIAM Symp. on Discrete Algorithms (SODA)*, 29-42, 2012. - S. Arya, G. D. da Fonseca, and D. M. Mount,
Approximate polytope membership queries,
*Proc. 43rd ACM Symp. on Theory of Computing (STOC)*, 579-586, 2011. - S. Arya, G. D. da Fonseca, and D. M. Mount,
A unified approach to approximate proximity searching,
*Proc. 18th European Symp. on Algorithms (ESA)*, 374-385, 2010. - S. Arya, T. Malamatos, and D. M. Mount,
Space-time tradeoffs for approximate nearest neighbor searching,
*Journal of the ACM*, 57(1), Article No. 1, 2009. (Also, in SODA 2002 and STOC 2002.) - S. Arya, D. M. Mount, A. Vigneron, and J. Xia,
Space-time tradeoffs for proximity searching in doubling spaces,
*Proc. 16th European Symp. on Algorithms (ESA)*, volume 5193 of Lecture Notes in Computer Science, 112-123, 2008. - S. Arya and H. Y. Fu,
Expected-case complexity of approximate nearest neighbor searching,
*SIAM Journal on Computing*, 32(3):793-815, 2003. (Also, in SODA 2000.) - S. Arya, T. Malamatos and D. M. Mount,
Space-efficient approximate Voronoi diagrams,
*Proc. 34th ACM Symp. on Theory of Computing (STOC)*, 721-730, 2002. - S. Arya and T. Malamatos,
Linear-size approximate Voronoi diagrams,
*Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (SODA)*, 147-155, 2002. - S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman and A. Wu,
An optimal algorithm for approximate nearest neighbor searching,
*Journal of the ACM*, 45(6):891-923, 1998. (Also, in SODA 1994.) - S. Arya, D. M. Mount and O. Narayan,
Accounting for boundary effects in nearest neighbor searching,
*Discrete and Computational Geometry*, 16:155-176, 1996. (Also, in SoCG 1995.) - S. Arya and D. M. Mount,
Approximate nearest neighbor queries in fixed dimensions,
*Proc. 4th ACM-SIAM Symp. on Discrete Algorithms (SODA)*, 271-280, 1993. (Revised.) - S. Arya and D. M. Mount,
Algorithms for fast vector quantization,
*Proc. IEEE Data Compression Conference (DCC)*, eds. J. A. Storer and M. Cohn, IEEE Press, 381-390, 1993. (Revised.)

### Approximate Range Searching:

- S. Arya, D. M. Mount, and E. Park,
Approximate geometric MST range queries,
*Proc. 31st Symp. on Computational Geometry (SoCG)*, 781-795, 2015. - S. Arya, D. M. Mount, and J. Xia,
Tight lower bounds for halfspace range searching,
*Discrete and Computational Geometry*, 47(4):711-730, 2012. (Also, in SoCG 2010.) - S. Arya, T. Malamatos and D. M. Mount,
The effect of corners on the complexity of approximate range searching,
*Discrete and Computational Geometry*, 41:398-443, 2009. (Also, in SoCG 2006.) - S. Arya, G. D. da Fonseca, and D. M. Mount,
Tradeoffs in approximate range searching made simpler,
*Proc. XXI Brazilian Symp. on Computer Graphics and Image Processing (SIBGRAPI)*, 237-244, 2008. - S. Arya, T. Malamatos, and D. M. Mount,
On the importance of idempotence,
*Proc. 38th ACM Symp. on Theory of Computing (STOC)*, 564-573, 2006. - S. Arya, T. Malamatos, and D. M. Mount,
Space-time tradeoffs for approximate spherical range counting,
*Proc. 16th ACM-SIAM Symp. on Discrete Algorithms (SODA)*, 535-544, 2005. - S. Arya and D. M. Mount,
Approximate range searching,
*CGTA*, 17:135-152, 2000.

### Planar Point Location:

- S. Arya, T. Malamatos, D. M. Mount and K. C. Wong,
Optimal expected-case planar point location,
*SIAM Journal of Computing*, 37(2), 584-610, 2007. (Based on Nearly optimal expected-case planar point location, FOCS 2000, and Entropy-preserving cuttings and space-efficient planar point location, SODA 2001.) - S. Arya, T. Malamatos and D. M. Mount,
A simple entropy-based algorithm for planar point location,
*ACM Trans. Algorithms*, 3(2), Article No. 17, 2007. (Also, in SODA 2001.) - S. Arya, S. W. Cheng, D. M. Mount and H. Ramesh,
Efficient expected-case algorithms for planar point location,
*Proc. 7th Scand. Workshop on Algorithm Theory (SWAT)*, 353-366, 2000.

### Euclidean Graphs and Spanners:

- S. Arya and D. M. Mount,
A fast and simple algorithm for computing approximate Euclidean minimum spanning trees,
*Proc. 27th ACM-SIAM Symp. on Discrete Algorithms (SODA)*, 1220-1233, 2016. - S. Arya, D. M. Mount and M. Smid,
Dynamic algorithms for geometric spanners of small diameter:
Randomized solutions,
*CGTA*, 13:91-107, 1999. - S. Arya and M. Smid,
Efficient construction of a bounded degree spanner with low weight,
*Algorithmica*, 17:33-54, 1997. (Also, in ESA 1994.) - S. Arya, G. Das, D. M. Mount, J. S. Salowe and M. Smid,
Euclidean spanners: Short, thin and lanky,
*Proc. 27th ACM Symp. on Theory of Computing (STOC)*, 489-498, 1995. -
S. Arya, D. M. Mount and M. Smid.
Randomized and deterministic algorithms for geometric spanners
of small diameter,
*Proc. 35th IEEE Symp. on Foundations of Computer Science (FOCS)*, 703-712, 1994.

### Approximation Algorithms for NP-hard Problems:

- V. S. Anil, S. Arya and H. Ramesh,
Hardness of set cover with intersection 1,
*Proc. 27th Internat. Colloq. Automata Lang. Prog. (ICALP)*, volume 1853 of LNCS, 624-635, 2000. - S. Arya, S. W. Cheng and D. M. Mount,
Approximation algorithms for multiple-tool milling,
*IJCGA*, 11(3):339-372, 2001. (Also, in SoCG 1998.) - S. Arya and H. Ramesh,
A 2.5 factor approximation algorithm for the k-MST problem,
*IPL*, 65(3):117-118, 1998.

### Other Topics:

- S. Arya,
Binary space partitions for axis-parallel line segments:
size-height tradeoffs,
*IPL*, 84(4):201-206, 2002. - S. Arya, M. Golin and K. Mehlhorn,
On the expected depth of random circuits,
*Combinatorics, Probability and Computing*, 8(3):209-228, 1999.