Papers in collection
- On the complexity of some
geometric problems in
unbounded dimension, by
N. Megiddo. In J. Symbolic Comput., 10: 327--334, 1990.
distance oracles for geometric spanners, by Gudmundsson,
Levcopoulos, Narasimhan and Smid.
- 3sumhard survey
- K. L. Clarkson. Nearest neighbor queries in
Discrete Comput. Geom., 22:63--93, 1999. Preliminary version in
Proc. 29th Symp. Theory Comput., 1997.
- Mehlhorn book:
- A decomposition of multidimensional
point sets with applications to k-nearest-neighbors and n-body
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
- Linear Time Algorithms for
Clustering Problems in any dimensions, by
Amit Kumar, Yogish Sabharwal,
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,
- 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 +
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.
Guarding art galleries by guarding witnesses, K. Chwa, B. Jo, C.
Knauer, Esther Moet, R. van Oostrum and C. Shin -
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