Range Searching and Its Relatives (Contemporary Mathematices 223, 1999)
P.K. Agarwal, J. Erickson

Estimating the Distance to a Monotone Function (RANDOM 2004)
N. Ailon, B. Chazelle, S. Comandur, D. Liu

Property Preserving Data Reconstruction (ISAAC 2004)
N. Ailon, B. Chazelle, S. Comandur, D. Liu

An Optimal Algorithm For Intersecting Three-Dimensional Convex Polyhedra (SIAM Journal on Computing: 21, 1992)
B. Chazelle

A Linear Time Algorithm for Determining the Separation of Convex Polyhedra (Journal of Algorithms: 6, 1985)
D. Dobkin, D. Kirkpatrick

Optimal Search in Planar Subdivisions (SIAM Journal on Computing: 12, 1983)
D. Kirkpatrick

A Separator Theorem for Planar Graphs (SIAM J. of App. Math: 36, 1979)
R. Lipton, R. Tarjan

Applications of a Planar Separator Theorem (FOCS 1977)
R. Lipton, R. Tarjan

Finding Small Simple Cycle Separators for 2-Connected Planar Graphs (JCSS: 32, 1986)
G. Miller

GEOMETRIC PROPERTY TESTING AND SUBLINEAR ALGORITHMS

Testing of Clustering (FOCS 2000)
N. Alon, S. Dar, M. Parnas, D. Ron

Sublinear Geometric Algorithms (STOC 2003)
B. Chazelle, D. Liu, A. Magen

Sublinear-time approximation of Euclidean minimum spanning tree (SODA 2003)
A. Czumaj, F. Ergun, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, C. Sohler

Property Testing with Geometric Queries (ESA 2001)
A. Czumaj, C. Sohler

Estimating the weight of metric minimum spanning trees in sublinear-time (STOC 2004)
A. Czumaj, C. Sohler

Testing Convex Position (http://www.cis.njit.edu/~czumaj/PUBLICATIONS/ESA-2000-Convex-positions.pdf)
A. Czumaj, C. Sohler, M. Ziegler

Property Testing in Computational Geometry (ESA 2000)
A. Czumaj, C. Sohler, M. Ziegler

A sublinear-time approximation scheme for clustering in metric spaces (STOC 1999)
P. Indyk

Sublinear-time algorithms for metric space problems (FOCS 1999)
P. Indyk

Checking Geometric Programs or Verification of Geometric Structures (SOCG 1996)
K. Mehlhorn, S. Näher, M. Seel, R. Seidel, T. Schilz, S. Schirra, C. Uhrig

Sublinear time approximate clustering (SODA 2001)
N. Mishra, D. Oblinger, L. Pitt

RECONSTRUCTION

An Efficient Algorithm for Terrain Simplification (SODA 1997)
P.K. Agarwal, P.K. Desikan

Translating a planar object to maximize point containment (ESA 2002)
P.K. Agarwal, T. Hagerup, R. Ray, M. Sharir, M. Smid, E. Welzl

Near-linear time approximation algorithms for curve simplification (Algorithmica submission)
P.K. Agarwal, S. Har-Peled, N. Mustafa, Y. Wang

Surface approximation and geometric partitions (SIAM J. Computing: 27, 1998)
P.K. Agarwal, S. Suri