Shape Analysis - Duke CPS 296.2 - Spring 2004
Basic representations
J. Gallier, Curves and Surfaces in Geometric Modeling: Theory and Algorithms, 1999.
A. Gshtasby, A. Rockwood, D. Terzopolos, A primer on shapes: Curves and surfaces, SIGGRAPH 2001, Course 7.
H. Pfister, A. Rockwood, et al., New directions in shape representations, SIGGRAPH 2001, Course 33.
Surface simplification
P.K. Agarwal and K.R. Varadarajan, Efficient algorithms for approximating polygonal chains, Discrete Computational Geometry, 23 (2000), 273-291.
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), 59-77.
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), 112-122.
M. Garland and P. Heckbert. Surface Simplification Using Quadric Error Metrics. In Proceedings of SIGGRAPH 97.
P. Heckbert and M. Garland. Survey of Polygonal Surface Simplification Algorithms. In SIGGRAPH 97 Course Notes: Multiresolution Surface Modeling.
H.Imai and M.Iri, Polygonal approximations of a curve-formulations and algorithms, in: Computational Morphology (G.T. Toussaint, ed.), North-Holland, Amsterdam, Netherlands, 1988, pp. 71-86.

Hierarchical representation

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

Deformable Shapes

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), 150-165.
M. L. Teodoro, G. N. Phillips, and L. E. Kavraki, Understanding protein flexibility through dimensional reduction, J. Computational Biology 10 (2003), 617-634.
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), 60-69.

Histograms and harmonic maps

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, 207-228.
[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), 83-105.
[GG] C. Gotsman, Xianfeng Gu, and A. Sheffer, Fundamentals of spherical parameterization for 3D Meshes, SIGGRAPH, 2003, 358-363.
[OF] R. Osada, T. Funkhouser, B. Chazelle, and D. P. Dobkin. Shape distributions. ACM Trans. Graph. 21 (2002), 807-832.

Medial axis and skeletons

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), 44-61.
[SS] K. Siddiqi, A. Shokoufandeh, S. J. Dickinson & S. W. Zucker. Shock Graphs and Shape Matching. Intl. J. Computer Vision, 35 (1999), 13-32.
[DP] P. Dimitrov, C. Phillips & K. Siddiqi. Robust and Efficient Skeletal Graphs. Proc. Annual Conference on Computer Vision and Pattern Recognition, 2000, 417-423.

Topology based methods

P. K. Agarwal, H. Edelsbrunner, J. Harer, and Y. Wang, Extreme elevation on a 2-manifold, submitted for publication, 2003.
[CC] F. Cazals, F. Chazal and T. Lewiner. Molecular shape analysis based upon the Morse-Smale complex and the Connolly function. Proc. 19th Ann. Sympos. Comput. Geom., 2003, 351-360.
[C] M. L. Connolly. Shape distributions of protein topography. Biopolymers 32(1992), 1215-1236.
[HS] M. Hilaga, Y. Shinagawa, T. Kohmura, T. L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proc. SIGGRAPH 2001, 203-212.
[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), 324-329.

[DM] I. Dryden and K. Mardia, Statistical Shape Analysis, John Wiley & Sons, 1998.
[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, 121-153.
[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), 1328-1338.
[LW] Y. Lamdan and H. Wolfson, Geometric hashing: A general and efficient model-based recognition scheme, Proc. IEEE 2nd Intl Conf. Computer Vision, 1988, 238-249.
[LK] H. Lee, J. Kittler, and K. Wong, Generalised Hough transform in object recognition, Proc. 11th IAPR Conf. on Pattern Recognition, 1992, 285-289.
[WR] H. Wolfson and I. Rigoutsos, Geometric hashing: An overview, IEEE Computational Science and Engineering, 4 (1997), 10-21.
Entropy-based methods
[VM] P. Viola and W. M. Wells III, Alignment by maximization of mutual information, Intl. Journal of Computer Vision, 24(1997) 137-154.
[RC] A. Rangarajan, H. Chui and J. S. Duncan, Rigid point feature registration using mutual information, Medical Image Analysis, 4(1999), 1-17.
[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. Har-Peled, M. Sharir and Y. Wang, Hausdorff distance under translation for points, disks and balls, Proc. 19th ACM Symp. on Computational Geometry (2003), 282-291.
[AA] H. Alt, O. Aichholzer, and G. Rote. Matching shapes with a reference point. Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 85-92, 1994.
[AG] H. Alt and M. Godau, Computing the Frechet distance between two polygonal curves, Internat. J. Comput. Geom. Appl. 5 (1995), 75-91.
[CS] D. Cardoze and L. Schulman, Pattern matching for spatial point sets. Proc. 38th IEEE Sympos Foundations of Computer Science, 1998, 156-165.
[HK] D.P. Huttenlocher and K. Kedem, Efficiently computing the Hausdorff distance for point sets under translation, Proc. 6th Annual Sympos. Comput. Geom., 1990, 340-349.
[HKS] D.P. Huttenlocher, K. Kedem, and M. Sharir, The upper envelope of Voronoi surfaces and its applications, Discrete Comput. Geom. 9 (1993), 267-291.
ICP and its variants
[BM] P. Besl and N. McKay, A method for registration of 3-D 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 intensity-based registration of 3D Volumes, Computer Vision and Image Understanding, 66 (1997), 193-206.
[RL] S. Rusinkiewicz and M. Levoy, Efficient Variants of the ICP Algorithm, Proc. 3rd Intl. Conf. on 3D Digital Imaging and Modeling, 2001, 145-152.
Graph-based methods
[AE] P. Agarwal, A. Efrat, and M. Sharir, Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, SIAM J. Computing 29 (2000), 912-953.
[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 non-bipartite matching in the plane, Proc. ACM-SIAM Symp. on Discrete Algorithms, 1999.
Edit distance and topological methods
Graph-based clustering methods
[HT] T. Hastie, R. Tibshirani, and J. Friedman. The Elements of
Statistical Learning, Springer-Verlag, 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), 412-458.
[BH] S. Badri and S. Har-Peled, On Lloyd's k-means Method,
unpublished manuscript, 2004.
[DF] Q. Du, V. Faber, and M. Gunzburger, Centroidal Voronoi Tesselations: Applications and Algorithms," SIAM
Review, 41 (1999), 637-676.
[HT] T. Hastie, R. Tibshirani, and J. Friedman. The Elements of
Statistical Learning, Springer-Verlag, Berlin, Germany, 2001.
[LV] J.-H. Lin and J. S. Vitter, e-approximations with minimum packing constraint violations, Proc. ACM Annu Sympos. Theory of Comput., 1992, 771-782.
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.
Nearest neighbor classification, decision trees
[HT] T. Hastie, R. Tibshirani, and J. Friedman. The Elements of
Statistical Learning, Springer-Verlag, Berlin, Germany, 2001.
[F] J. H. Friedman, Flexible metric nearest neighbor classification. Technical Report 113, Stanford University Statistics Department 1994.
Kernel based methods, support vector machines
R-trees and other bounding box hierarchies
Searching 3D protein databases