- On the complexity of some
geometric problems in
unbounded dimension, by
N. Megiddo. In J. Symbolic Comput., 10: 327--334, 1990.

- Approximate
distance oracles for geometric spanners, by Gudmundsson,
Levcopoulos, Narasimhan and Smid.

- 3sumhard survey
- 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. - Mehlhorn book: CH 1, CH 2, CH 3, CH 4, CH 5, CH 6, CH 7, CH 8.
- 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 - On enclosing $k$ points by a circle, by Matousek. From Inform. Process. Lett., 53:217--221, 1995.
- Strongly-Logarithmic Approximate Nearest-Neighbor Searching, by Christian A. Duncan.
- SpaceTime Tradeoffs for Approximate Spherical Range Counting by Sunil Arya, Theocharis Malamatos and David M. Mount.
- The Complexity of LowDistortion Embeddings Between Point Sets by Christos Papadimitriou and Shmuel Safra.
- Linear Time Algorithms for Clustering Problems in any dimensions, by Amit Kumar, Yogish Sabharwal, Hauz Khas, and Sandeep Sen.
- The Reset Model for Data Streams, by M. Homann, S. Muthukrishnan, and R. Raman 1
- Subgradient and Sampling Algorithms for L1 Regression, by Kenneth L. Clarkson.
- Shortest Path for Disc Obstacles with Rational Radii is Computable, by EeChien Chang, Sung Woo Choi, DoYong Kwon, Hyungju Park, Chee K. Ya.
- Pianos are not flat: Rigid motion planning in three dimensions, by Vladlen Koltun.
- 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.
**Linear Time Algorithms for Clustering Problems in any dimensions**, by by Amit Kumar, Yogish Sabharwal Sandeep Sen. Submitted to SODA 05.**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.**961**: Rapid clustering with a deterministic data net, M. Effros and L. J. Schulman.**959**: Guarding art galleries by guarding witnesses, K. Chwa, B. Jo, C. Knauer, Esther Moet, R. van Oostrum and C. Shin -**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 |