Recent Publications:
Polytope Approximation:
- S. Arya and D. M. Mount, Optimal volume-sensitive bounds for polytope approximation, Proc. 39th Internat. Symp. on Computational Geometry (SoCG), 2023.
- S. Arya, G. D. da Fonseca, and D. M. Mount, Economical convex coverings and applications, Proc. 34th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1834-1861, 2023.
- R. Arya, S. Arya, G. D. da Fonseca, and D. M. Mount, Optimal bound on the combinatorial complexity of approximating polytopes, ACM Trans. Algorithms, 18(4), Article No. 35, 2022. (Also, in SODA 2020.)
- 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, 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.
Approximate Nearest Neighbor Searching:
- 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 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, 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.