SoCG 2001 accepted papers

[David Eppstein]

The following papers have been accepted to the 17th ACM Symposium on
Computational Geometry, to be held June 3-5, 2001, at Tufts University,
Medford, MA.  For more information about the conference, see its web page,
<http://www.eecs.tufts.edu/EECS/scg01/>.  This list includes papers from
both the theory and applied tracks, but does not include the video
program, which is not scheduled to be announced until March 1.


Box-Trees and R-Trees with Near-Optimal Query Time,
Pankaj K. Agarwal and Mark de Berg and Joachim Gudmundsson and Mikael
Hammar and Herman J. Havekort

On the Number of Congruent Simplices in a Point Set,
Pankaj K. Agarwal and Micha Sharir

Enumerating Order Types for Small Point Sets with Applications,
O. Aichholzer and F. Aurenhammer and H. Krasser

Exact $L_\infty$ Nearest Neighbor Search in High Dimensions,
Helmut Alt and Laura Heinrich-Litan

A Sum of Squares Theorem for Visibility Complexes,
Pierre Angelier and Michel Pocchiola

New Bounds on the Betti Numbers of Semi-Algebraic Sets and Arrangements of
Real Algebraic Hypersurfaces,
Saugata Basu

Farthest Neighbors and Center Points in the Presence of Rectangular
Obstacles,
Boaz Ben-Moshe and Matthew J. Katz and Joseph S. B. Mitchell

A Segment-Tree Based Kinetic BSP,
Mark de Berg and Joao Comba and Leonidas J. Guibas

Schematization of Road Networks,
Sergio Cabello and Mark de Berg and Steven van Dijk and Marc van Kreveld
and Tycho Strijk

A Fully Dynamic Algorithm for Planar Width,
Timothy M. Chan

Algorithms for Congruent Sphere Packing and Applications,
Danny Z. Chen and Xiaobo (Sharon) Hu and Yingping Huang and Yifan Li
and Jinhui Xu

Walking in a Triangulation,
Olivier Devillers and Sylvain Pion and Monique Teillaud

Detecting Undersampling in Surface Reconstruction,
Tamal K. Dey and Joachim Giesen

Efficient and Small Representation of Line Arrangements with
Applications,
David P. Dobkin and Ayellet Tal

Binary Space Partitions for Axis-Parallel Segments, Rectangles, and
Hyperrectangles,
Adrian Dumitrescu and Joseph S. B. Mitchell and Micha Sharir

Sink-insertion for Mesh Improvement,
Herbert Edelsbrunner and Damrong Guoy

Hierarchical Morse Complexes for Piecewise Linear 2-Manifolds,
Herbert Edelsbrunner and John Harer and Afra Zomorodian

Nice Point Sets Can Have Nasty Delaunay Triangulations,
Jeff Erickson

Simplifying a Polygonal Subdivision While Keeping it Simple,
Regina Estkowski and Joseph S. B. Mitchell

Discrete Mobile Centers,
Jie Gao and Leonidas J. Guibas and John Hershberger and Li Zhang and An Zhu

polymake: an Approach to Modular Software Design in Computational
Geometry,
Ewgenij Gawrilow and Michael Joswig

Computing the Intersection of Quadrics: Exactly and Actually!,
Nicola Geismann and Michael Hemmer and Elmar Schoemer

A Randomized Art-Gallery Algorithm for Sensor Placement,
Hector Gonzalez-Banos and Jean-Claude Latombe

A Practical Approach for Computing the Diameter of a Point-Set,
Sariel Har-Peled

Notes on Computing Peaks in k-Levels and Parametric Spanning Trees,
Naoki Katoh and Takeshi Tokuyama

Geometric Permutations of Fat Objects,
Matthew Katz and Kasturi Varadarajan

Intersection Searching Problems in General Settings,
Vladlen Koltun

PRECISE: Efficient Multiprecision Evaluation of Algebraic Roots and
Predicates for Reliable Geometric Computation,
S. Krishnan and M. Foskey and T.  Culver and J. Keyser and D. Manocha

On the Complexity of Halfspace Area Queries,
Stefan Langerman

Computing a Canonical Polygonal Schema of an Orientable
Triangulated Surface,
Francis Lazarus and Michel Pocchiola and Gert Vegter and Anne Verroust

Hardware-Assisted View-Dependent Map Simplification,
Nabil Mustafa and Eleftheris Koutsofios and Shankar Krishnan and
Suresh Venkatasubraminian

The Union of Congruent Cubes in Three Dimensions,
Janos Pach and Ido Safruti and Micha Sharir

Efficient Perspective-Accurate Silhouette Computation and
Applications,
Mihai Pop and Gill Barequet and Christian A. Duncan and
Michael T. Goodrich and Wenjing Huang and Subodh Kumar

Monotone Paths in Line Arrangements,
Rados Radoicic and Geza Toth

Area-Preserving Piecewise-Affine Transformations,
Alan Saalfeld

The Clarkson-Shor Technique Revisited and Extended,
Micha Sharir

Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem,
Micha Sharir and Emo Welzl

Different Distances of Planar Point Sets,
Jozsef Solymosi and Csaba David Toth

A Note on Binary Plane Partitions,
Csaba David Toth

-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.