Papers in collection

    1. On the complexity of some geometric problems in unbounded dimension, by N. Megiddo. In J. Symbolic Comput., 10: 327--334, 1990.
    2. Approximate distance oracles for geometric spanners, by Gudmundsson, Levcopoulos, Narasimhan and Smid.
    3. 3sumhard survey
    4. K. L. Clarkson. Nearest neighbor queries in metric spaces
      Discrete Comput. Geom., 22:63--93, 1999. Preliminary version in Proc. 29th Symp. Theory Comput., 1997.
    5. Mehlhorn book: CH 1, CH 2, CH 3, CH 4, CH 5, CH 6, CH 7, CH 8.
    6. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields by Paul B. Callahan and S. Rao Kosaraju.
      From JACM Volume 42 , Issue 1 (January 1995) table of contents Pages: 67 - 90 Year of Publication: 1995 ISSN:0004-5411 Authors
    7. On enclosing $k$ points by a circle, by Matousek. From Inform. Process. Lett., 53:217--221, 1995.
    8. Strongly-Logarithmic Approximate Nearest-Neighbor Searching, by Christian A. Duncan.
    9. Space­Time Tradeoffs for Approximate Spherical Range Counting by Sunil Arya, Theocharis Malamatos and David M. Mount.
    10. The Complexity of Low­Distortion Embeddings Between Point Sets by Christos Papadimitriou and Shmuel Safra.
    11. Linear Time Algorithms for Clustering Problems in any dimensions, by Amit Kumar, Yogish Sabharwal, Hauz Khas, and Sandeep Sen.
    12. The Reset Model for Data Streams, by M. Homann, S. Muthukrishnan, and R. Raman 1
    13. Subgradient and Sampling Algorithms for L1 Regression, by Kenneth L. Clarkson.
    14. Shortest Path for Disc Obstacles with Rational Radii is Computable, by Ee­Chien Chang, Sung Woo Choi, DoYong Kwon, Hyungju Park, Chee K. Ya.
    15. Pianos are not flat: Rigid motion planning in three dimensions, by Vladlen Koltun.
    16. Algorithms for vertical and orthogonal L1 linear approximation of points, P. Yamamoto, K. Kato, K. Imai, and H. Imai. In SoCG 1988, pages 352-361.
    17. Linear Time Algorithms for Clustering Problems in any dimensions, by by Amit Kumar, Yogish Sabharwal Sandeep Sen. Submitted to SODA 05.
    18. A simple linear time (1 + eps)-approximation algorithm for k-means clustering in any dimensions, by Amit Kumar Yogish Sabharwal Sandeep Sen. To appear in FOCS 2004.
    19. 961: Rapid clustering with a deterministic data net, M. Effros and L. J. Schulman.
    20. 959: Guarding art galleries by guarding witnesses, K. Chwa, B. Jo, C. Knauer, Esther Moet, R. van Oostrum and C. Shin -
    21. 459: Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu: An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions. J. ACM 45(6): 891-923 (1998)

Last modified: Fri Mar 24 16:32:09 CST 2006
Home Bookmarks Papers Blog