




Basic
representations 
[Gal] 
J. Gallier, Curves and Surfaces in
Geometric Modeling: Theory and Algorithms, 1999. 
[GR] 
A. Gshtasby, A. Rockwood, D. Terzopolos,
A primer on shapes:
Curves and surfaces, SIGGRAPH 2001, Course 7. 
[PR] 
H. Pfister, A. Rockwood, et al.,
New directions in shape
representations, SIGGRAPH 2001, Course 33. 

Surface
simplification 
[AV] 
P.K. Agarwal and K.R. Varadarajan,
Efficient algorithms for approximating polygonal chains,
Discrete Computational Geometry, 23 (2000), 273291. 
[CC] 
W.S. Chan and F.Chin, Approximation
of polygonal curves with minimum number of line segments
or minimum error, International Journal Computational
Geometry Applications, 6 (1996), 5977. 
[DP] 
D.H. Douglas and T.K. Peucker, Algorithms
for the reduction of the number of points required to
represent a digitized line or its caricature., The Canadian
Cartographer, 10 (1973), 112122. 
[GH] 
M. Garland and P. Heckbert. Surface
Simplification Using Quadric Error Metrics. In Proceedings
of SIGGRAPH 97. 
[HG] 
P. Heckbert and M. Garland. Survey
of Polygonal Surface Simplification Algorithms. In
SIGGRAPH 97 Course Notes: Multiresolution Surface Modeling. 
[II] 
H.Imai and M.Iri, Polygonal approximations
of a curveformulations and algorithms, in: Computational
Morphology (G.T. Toussaint, ed.), NorthHolland, Amsterdam,
Netherlands, 1988, pp. 7186. 

Hierarchical
representation 
[Gal] 
J. Gallier, Curves and Surfaces in
Geometric Modeling: Theory and Algorithms, 1999 
[Gar] 
M. Garland, Multiresolution
modeling: Survey and future opportunities, Eurographics
'99, State of the Art Report, 1999. 
[SD] 
E. Stollnitz, T. D. Derose, and D.
H. Salesin, Wavelets for Computer Graphics, Morgan Kaufmann,
1996. 

Deformable
Shapes 
[JR] 
D. J. Jacobs, A. J. Rader,
L. A. Kuhn, and M. F. Thorpe, Protein
flexibility predictions using graph theory, Proteins:
Structure, Function, and Genetics 44 (2001), 150165. 
[TP] 
M. L. Teodoro, G. N. Phillips, and
L. E. Kavraki, Understanding
protein flexibility through dimensional reduction,
J. Computational Biology 10 (2003), 617634. 
[TL] 
M. Thorpe, M. Lei, A. J. Rader, D.
J. Jacobs, and L. A. Kuhn, Protein
flexibility and dynamics using constraint theory,
J. Molecular Graphics and Modeling, 19 (2001), 6069. 


Histograms
and harmonic maps 
[AK] 
M. Ankerst, G. Kastenm?ller,
H. Kriegel, and T. Seidl, 3D Shape
histograms for similarity search and classification in
spatial databases Proc. 6th Intl. Sympos. in Advances
in Spatial Databases, 1999, 207228. 
[FM] 
T. Funkhouser, P. Min, M. Kazhdan,
J. Chen, A. Halderman, D. Dobkin, and D. Jacobs, A
search engine for 3D models. ACM Transactions on Graphics,
22 (2003), 83105. 
[GG] 
C. Gotsman, Xianfeng Gu, and A.
Sheffer, Fundamentals
of spherical parameterization for 3D Meshes, SIGGRAPH,
2003, 358363. 
[OF] 
R. Osada, T. Funkhouser, B. Chazelle,
and D. P. Dobkin. Shape
distributions. ACM Trans. Graph. 21 (2002), 807832. 
Medial
axis and skeletons 
[SP] 
E. Sherbrooke, N. Patrikalakis,
and E. Brisson, An
algorithm for the medial axis transform of 3D polyhedral
solids, IEEE Trans. Visualization & Computer Graphics,
2 (1996), 4461. 
[SS] 
K. Siddiqi, A. Shokoufandeh, S.
J. Dickinson & S. W. Zucker. Shock
Graphs and Shape Matching. Intl. J. Computer Vision,
35 (1999), 1332. 
[DP] 
P. Dimitrov, C. Phillips & K.
Siddiqi. Robust and Efficient
Skeletal Graphs. Proc. Annual Conference on Computer
Vision and Pattern Recognition, 2000, 417423. 
Topology
based methods 
[AK] 
P. K. Agarwal, H. Edelsbrunner,
J. Harer, and Y. Wang, Extreme elevation on a 2manifold,
submitted for publication, 2003. 
[CC] 
F. Cazals, F. Chazal and T. Lewiner.
Molecular shape analysis based upon the MorseSmale complex
and the Connolly function. Proc. 19th Ann. Sympos. Comput.
Geom., 2003, 351360. 
[C] 
M. L. Connolly. Shape distributions
of protein topography. Biopolymers 32(1992), 12151236. 
[HS] 
M. Hilaga, Y. Shinagawa, T. Kohmura,
T. L. Kunii, Topology matching for fully automatic similarity
estimation of 3D shapes, Proc. SIGGRAPH 2001, 203212. 
[MK] 
J. C. Mitchell, R. Kerr and L. F.
Ten Eyck. Rapid atomic density measures for molecular
shape characterization. J. Mol. Graph. Model. 19 (2001),
324329. 

[DM] 
I. Dryden and K. Mardia, Statistical
Shape Analysis, John Wiley & Sons, 1998. 

Surveys 
[AG] 
H. Alt and L. Guibas, Discrete geometric shapes: Matching,
interpolation, and approximation, in Handbook of Computational
Geometry, (J.R. Sack and J. Urrutia, eds.), Elsevier,
1999, 121153. 
[Ve] 
R. C. Veltkamp, Shape matching: Similarity measures
and algorithms, Tech Rept, Utrecht University, 2001. 
Geometric
Hashing and Hough Transform 
[HB] 
Y. Hecker and R. Bolle, On Geometric Hashing and the
Generalized Hough Transform, IEEE Transactions on Systems,
Man, and Cybernetics, 24 (1994), 13281338. 
[LW] 
Y. Lamdan and H. Wolfson, Geometric hashing: A general
and efficient modelbased recognition scheme, Proc. IEEE
2nd Intl Conf. Computer Vision, 1988, 238249. 
[LK] 
H. Lee, J. Kittler, and K. Wong, Generalised Hough
transform in object recognition, Proc. 11th IAPR Conf.
on Pattern Recognition, 1992, 285289. 
[WR] 
H. Wolfson and I. Rigoutsos, Geometric hashing: An
overview, IEEE Computational Science and Engineering,
4 (1997), 1021. 
Entropybased
methods 
[VM] 
P. Viola and W. M. Wells
III, Alignment by maximization of mutual information,
Intl. Journal of Computer Vision, 24(1997) 137154. 
[RC] 
A. Rangarajan, H. Chui
and J. S. Duncan, Rigid point feature registration using
mutual information, Medical Image Analysis, 4(1999), 117. 
[CG] 
S. Cohen and L. Guibas.
The earth mover's distance under transformation sets.
Proc. 7th IEEE Intl. Conf. on Computer Vision, 1999. 
Hausdorff
and Frechet distances 
[AH] 
P. Agarwal, S. HarPeled, M. Sharir and Y. Wang, Hausdorff
distance under translation for points, disks and balls,
Proc. 19th ACM Symp. on Computational Geometry (2003),
282291. 
[AA] 
H. Alt, O. Aichholzer, and G. Rote. Matching shapes
with a reference point. Proc. 10th Annu. ACM Sympos. Comput.
Geom., pages 8592, 1994. 
[AG] 
H. Alt and M. Godau, Computing the Frechet distance
between two polygonal curves, Internat. J. Comput. Geom.
Appl. 5 (1995), 7591. 
[CS] 
D. Cardoze and L. Schulman, Pattern matching for spatial
point sets. Proc. 38th IEEE Sympos Foundations of Computer
Science, 1998, 156165. 
[HK] 
D.P. Huttenlocher and K. Kedem, Efficiently computing
the Hausdorff distance for point sets under translation,
Proc. 6th Annual Sympos. Comput. Geom., 1990, 340349.

[HKS] 
D.P. Huttenlocher, K. Kedem, and M. Sharir, The upper
envelope of Voronoi surfaces and its applications, Discrete
Comput. Geom. 9 (1993), 267291. 
ICP and
its variants 
[BM] 
P. Besl and N. McKay, A method for registration of
3D shapes, IEEE Trans. on Pattern Analysis and Machine
Intelligence, 14 (1992), 
[FM] 
J. Feldmar, G. Malandain, J. Declerck, and N. Ayache,
Extension of the ICP algorithm to nonrigid intensitybased
registration of 3D Volumes, Computer Vision and Image
Understanding, 66 (1997), 193206. 
[RL] 
S. Rusinkiewicz and M. Levoy, Efficient Variants of
the ICP Algorithm, Proc. 3rd Intl. Conf. on 3D Digital
Imaging and Modeling, 2001, 145152. 
Graphbased
methods 
[AE] 
P. Agarwal, A. Efrat, and M. Sharir, Vertical decomposition
of shallow levels in 3dimensional arrangements and its
applications, SIAM J. Computing 29 (2000), 912953. 
[La] 
E. Lawler, Combinatorial optimization: Networks and
Matroids. Holt, Rinehart, and Winston, NY, 1976. 
[VA] 
K. R. Varadarajan and P. K. Agarwal, Approximation
algorithms for bipartite and nonbipartite matching in
the plane, Proc. ACMSIAM Symp. on Discrete Algorithms,
1999. 
Edit distance and
topological methods 

Graphbased
clustering methods 
[HT] 
T. Hastie, R. Tibshirani, and J. Friedman. The Elements
of
Statistical Learning, SpringerVerlag, Berlin, Germany,
2001. 
[SS] 
R. Shamir and R. Sharan. Algorithmic approaches to
clustering gene expression data, In T. Jiang, T. Smith,
Y. Xu, and M. Q. Zhang, editors, Current Topics in Computational
Biology. MIT press, 2001. 
[TH] 
R. Tibshirani, T. Hastie, M. Eisen, D. Ross, D. Botstein,
and P. Brown. Clustering methods for the analysis of dna
microarray data, Technical report, Department of Health
Research and Policy, Stanford University, 1999. 
Geometric
clustering 
[AS] 
P. K. Agarwal and M. Sharir, Efficient algorithms for
geometric optimization, ACM Computing Surveys 30 (1998),
412458. 
[BH] 
S. Badri and S. HarPeled, On Lloyd's kmeans Method,
unpublished manuscript, 2004. 
[DF] 
Q. Du, V. Faber, and M. Gunzburger, Centroidal Voronoi
Tesselations: Applications and Algorithms," SIAM
Review, 41 (1999), 637676. 
[HT] 
T. Hastie, R. Tibshirani, and J. Friedman. The Elements
of
Statistical Learning, SpringerVerlag, Berlin, Germany,
2001. 
[LV] 
J.H. Lin and J. S. Vitter, eapproximations with minimum
packing constraint violations, Proc. ACM Annu Sympos.
Theory of Comput., 1992, 771782. 
Spectral
and embedding methods 
[NJ] 
A. Ng, M. Jordan, and Y. Weiss, On spectral clustering:
Analysis and an algorithm, Proc. 14th Symposium on Advances
in Neural Information Processing Systems, 2001. 
[KV] 
R. Kannan, S. Vempala, and A. Vetta, On clusterings
 good, bad and spectral, in Proc. 41st Symposium on the
Foundation of Computer Science, FOCS, 2000. 
[SM] 
J. Shi and J. Malik, Normalized Cuts and Image Segmentation,
in Proc. of IEEE Conf. on Comp. Vision and Pattern Recognition,
1997. 
[VM] 
D. Verma and M. Meila, Comparison of Spectral Clustering
Methods, manuscript. 
Kernel
based methods, support vector machines 

Rtrees and other
bounding box hierarchies 
Searching 3D protein
databases 



