List of accepted papers for SOCG 2004: Pushing squares around Adrian Dumitrescu and János Pach Counting and Representing Intersections Among Triangles in Three Dimensions Ester Ezra and Micha Sharir On the Delaunay Graph of a Geometric Graph Rom Pinchasi and Shakhar Smorodinsky On distinct distances from a vertex of a convex polygon Adrian Dumitrescu Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve Ilya Baran, Erik D. Demaine Low-Dimensional Embedding with Extra Information Mihai Badoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Piotr Indyk On Lines Avoiding Unit Balls in Three Dimensions Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, Micha Sharir On the Union of kappa-Round Objects in Three and Four Dimensions Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir Deterministic Sampling and Range Counting in Geometric Data Streams Amitabha Bagchi and Amitabh Chaudhary and David Eppstein and Michael T. Goodrich Binary Space Partitions of Orthogonal Subdivisions John Hershberger, Subhash Suri, and Csaba D. Toth On Empty Convex Polygons in a Planar Point Set Rom Pinchasi, Rados Radoicic and Micha Sharir Computing Persistent Homology Afra Zomorodian and Gunnar Carlsson Complete, Exact, and Efficient Computations with Cubic Curves Arno Eigenwillig, Lutz Kettner, Elmar Schömer, Nicola Wolpert The Criss-Cross Method Can Take ?(nd) Pivots Komei Fukuda and Bohdan Kaluzny A Near-Linear Constant-Factor Approximation for Euclidean Bipartite Matching? Pankaj Agarwal and Kasturi Varadarajan Continuous Path Verification in Multi-Axis NC-Machining Ron Wein, Oleg Ilushin, Gershon Elber and Dan Halperin Provable Surface Reconstruction from Noisy Samples Tamal K. Dey and Samrat Goswami Faster Core-Set Constructions and Data Stream Algorithms in Fixed Dimensions Timothy M. Chan Towards In-Place Geometric Algorithms and Data Structures Hervé Brönnimann, Timothy M. Chan, and Eric Y. Chen Extreme elevation on a 2-manifold Pankaj K. Agarwal, Herbert Edelsbrunner, John Harer and Yusu Wang An Empirical Comparison of Techniques for Updating Delaunay Triangulations Leonidas Guibas, Daniel Russel Geodesic Ham-Sandwich Cuts Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin Locality-Sensitive Hashing Scheme Based on p-Stable Distributions Mayur Datar and Nicole Immorlica and Piotr Indyk and Vahab Mirrokni Finding Planar Regions in a Terrain - In Practice and with a Guarantee Stefan Funke, Theocharis Malamatos, Rahul Ray Separating point sets in polygonal environments Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, Sue Whitesides Algorithms for Center and Tverberg Points Pankaj K. Agarwal, Micha Sharir, Emo Welzl Practical Methods for Shape Fitting and Kinetic Data Structures using Core Sets Pankaj K. Agarwal, Raghunath Poreddy, Kasturi R. Varadarajan, Hai Yu Time-varying Contour Trees for Continuous Space-Time Data Herbert Edelsbrunner, John Harer, Ajith Mascarenhas, Valerio Pascucci Improving the Crossing Lemma by finding more crossings in sparse graphs János Pach, Rados Radoicic, Gabor Tardos, Geza Toth Sampling and Meshing a Surface with Guaranteed Topology and Geometry Siu-Wing Cheng, Tamal K. Dey, Edgar Ramos and Tathagata Ray The Number of Lines Tangent to Arbitrary Polytopes in R3 Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sue Whitesides Intersecting Quadrics: An Efficient and Exact Implementation Sylvain Lazard, Luis Mariano Penaranda, Sylvain Petitjean Solution of Scott's problem on the number of directions determined by a point set in 3-space János Pach, Rom Pinchasi, Micha Sharir A 2D Kinetic Triangulation with Near-Quadratic Topological Changes Pankaj K. Agarwal, Yusu Wang, and Hai Yu Inner and Outer Rounding of Set Operations on Lattice Polygonal Regions Olivier Devillers and Philippe Guigue New Results on Shortest Paths in Three Dimensions Joseph Mitchell and Micha Sharir On the Least Median Square Problem Jeff Erickson, Sariel Har-Peled and David Mount Deformable Spanners and their Applications Jie Gao, Leonidas J. Guibas, An Nguyen Quality Meshing for Polyhedra with Small Angles Siu-Wing Cheng, Tamal K. Dey, Edgar Ramos and Tathagata Ray Spacetime Meshing with Adaptive Refinement and Coarsening Reza Abedi, Shuo-Heng Chung, Jeff Erickson, Yong Fan, Michael Garland, Damrong Guoy, Robert Haber, John M. Sullivan, Shripad Thite, and Yuan Zhou (updated author list, 4/02/2004) Approximate Convex Decomposition of Polygons Jyh-Ming Lien and Nancy M. Amato Computing the Visibility Graph of Points Within a Polygon Boaz Ben-Moshe, Olaf Hall-Holt, Matthew Katz, and Joseph Mitchell Range Counting over Multidimensional Data Streams Subhash Suri, Csaba D. Toth, and Yunhong Zhou The Geometric Thickness of Low Degree Graphs Christian A. Duncan, David Eppstein, Stephen G. Kobourov A Bezier-Based Approach to Unstructured Moving Meshes Gary Miller, David Cardoze, Todd Phillips A Scalable Simulator for Forest Dynamics Sathish Govindarajan, Mike Dietze, Pankaj K Agarwal, James Clark A Computational Framework for Incremental Motion David M. Mount, Nathan S. Netanyahu, Christine Piatko, Ruth Silverman, Angela Y. Wu An Energy-Driven Approach to Linkage Unfolding Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, and James F. O'Brien Towards an open curved kernel Ioannis Z. Emiris, Athanasios V. Kakargias, Sylvain Pion, Monique Teillaud, Elias P. Tsigaridas