ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
      Please provide us with feedback. Feedback
 
Annual Symposium on Computational Geometry archive
Proceedings of the nineteenth annual symposium on Computational geometry
2003,  San Diego, California, USA    June 08 - 10, 2003
Additional Information:full citation, abstract
Paper Acceptance Rate:42 of 118 submissions, 36%  view statistics
Conference Chair   
Steve Fortune Bell Laboratories
 
Table of Contents
 
SESSION: Geometric graphs
    Fault-tolerant geometric spanners
Artur Czumaj, Hairong Zhao
Pages: 1 - 10
Full text available: pdf formatPdf(267 KB)
Additional Information:full citation, abstract, references, index terms
    Euclidean bounded-degree spanning tree ratios
Timothy M. Chan
Pages: 11 - 19
Full text available: pdf formatPdf(227 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Approximation algorithms for aligning points
Sergio Cabello, Marc van Kreveld
Pages: 20 - 28
Full text available: pdf formatPdf(248 KB)
Additional Information:full citation, abstract, references, index terms
 
 
SESSION: Approximation
    Shape fitting with outliers
Sariel Har-Peled, Yusu Wang
Pages: 29 - 38
Full text available: pdf formatPdf(288 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    High-dimensional shape fitting in linear time
Sariel Har-Peled, Kasturi Varadarajan
Pages: 39 - 47
Full text available: pdf formatPdf(234 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Smooth kinetic maintenance of clusters
John Hershberger
Pages: 48 - 57
Full text available: pdf formatPdf(284 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Applications
    Polygon decomposition based on the straight line skeleton
Mirela Tanase, Remco C. Veltkamp
Pages: 58 - 67
Full text available: pdf formatPdf(365 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Efficient algorithms for shared camera control
Sariel Har-Peled, Vladlen Koltun, Dezhen Song, Ken Goldberg
Pages: 68 - 77
Full text available: pdf formatPdf(321 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Good NEWS: partitioning a simple polygon by compass directions
Marc van Kreveld, Iris Reinbacher
Pages: 78 - 87
Full text available: pdf formatPdf(309 KB)
Additional Information:full citation, abstract, references, index terms
    Geometric algorithms for static leaf sequencing problems in radiation therapy
Danny Z. Chen, Xiaobo S. Hu, Shuang Luan, Chao Wang
Pages: 88 - 97
Full text available: pdf formatPdf(235 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Combinatorial geometry
    Topological graphs with no self-intersecting cycle of length 4
Rom Pinchasi, Radoa Radoicic
Pages: 98 - 103
Full text available: pdf formatPdf(255 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Distinct distances in homogeneous sets
Jazsef Solymosi, Van H. Vu
Pages: 104 - 105
Full text available: pdf formatPdf(109 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    A tight bound for the number of different directions in three dimensions
Janos Pach, Rom Pinchasi, Micha Sharir
Pages: 106 - 113
Full text available: pdf formatPdf(270 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    On conflict-free coloring of points and simple regions in the plane
Sariel Har-Peled, Shakhar Smorodinsky
Pages: 114 - 123
Full text available: pdf formatPdf(247 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Partitions and arrangements
    Long monotone paths in line arrangements
Jazsef Balogh, Oded Regev, Clifford Smyth, William Steiger, Mario Szegedy
Pages: 124 - 128
Full text available: pdf formatPdf(199 KB)
Additional Information:full citation, abstract, references, index terms
    New constructions of weak epsilon-nets
Jivri Matouaek
Pages: 129 - 135
Full text available: pdf formatPdf(273 KB)
Additional Information:full citation, abstract, references, index terms
    Curve-sensitive cuttings
Vladlen Koltun, Micha Sharir
Pages: 136 - 143
Full text available: pdf formatPdf(213 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Motion and pseudotriangulations
    Spatial embedding of pseudo-triangulations
Oswin Aichholzer, Franz Aurenhammer, Peter Braay
Pages: 144 - 153
Full text available: pdf formatPdf(257 KB)
Additional Information:full citation, abstract, references, index terms
    Planar minimally rigid graphs and pseudo-triangulations
Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Hermann Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley
Pages: 154 - 163
Full text available: pdf formatPdf(283 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    The complexity of (un)folding
Helmut Alt, Christian Knauer, Günter Rote, Sue Whitesides
Pages: 164 - 170
Full text available: pdf formatPdf(228 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Models and meshes
    Local polyhedra and geometric graphs
Jeff Erickson
Pages: 171 - 180
Full text available: pdf formatPdf(362 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Updating and constructing constrained delaunay and constrained regular triangulations by flips
Jonathan Richard Shewchuk
Pages: 181 - 190
Full text available: pdf formatPdf(326 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Anisotropic voronoi diagrams and guaranteed-quality anisotropic mesh generation
Francois Labelle, Jonathan Richard Shewchuk
Pages: 191 - 200
Full text available: pdf formatPdf(423 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Complexity of the delaunay triangulation of points on surfaces the smooth case
Dominique Attali, Jean-Daniel Boissonnat, André Lieutier
Pages: 201 - 210
Full text available: pdf formatPdf(394 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Incremental constructions con BRIO
Nina Amenta, Sunghee Choi, Günter Rote
Pages: 211 - 219
Full text available: pdf formatPdf(485 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Data structures
    Proximate planar point location
John Iacono, Stefan Langerman
Pages: 220 - 226
Full text available: pdf formatPdf(230 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Cost-driven octree construction schemes: an experimental study
Boris Aronov, Hervé Bronnimann, Allen Y. Chang, Yi-Jen Chiang
Pages: 227 - 236
Full text available: pdf formatPdf(581 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Cache-oblivious data structures for orthogonal range searching
Pankaj K. Agarwal, Lars Arge, Andrew Danner, Bryan Holland-Minkley
Pages: 237 - 245
Full text available: pdf formatPdf(353 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Numerical issues and robustness
    Near-optimal parameterization of the intersection of quadrics
Laurent Dupont, Daniel Lazard, Sylvain Lazard, Sylvain Petitjean
Pages: 246 - 255
Full text available: pdf formatPdf(322 KB)
Additional Information:full citation, abstract, references, cited by, index terms, review
    Constructive root bound for <tt>k</tt>-ary rational input numbers
Sylvain Pion, Chee K. Yap
Pages: 256 - 263
Full text available: pdf formatPdf(243 KB)
Additional Information:full citation, abstract, references, index terms
    Controlled perturbation for arrangements of circles
Dan Halperin, Eran Leiserowitz
Pages: 264 - 273
Full text available: pdf formatPdf(606 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Optimization
    Optimized color gamuts for tiled displays
Marshall Bern, David Eppstein
Pages: 274 - 281
Full text available: pdf formatPdf(155 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Hausdorff distance under translation for points and balls
Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, Yusu Wang
Pages: 282 - 291
Full text available: pdf formatPdf(275 KB)
Additional Information:full citation, abstract, references, index terms
    The smallest enclosing ball of balls: combinatorial structure and algorithms
Kaspar Fischer, Bernd Gartner
Pages: 292 - 301
Full text available: pdf formatPdf(326 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Curve and surface reconstruction
    Curve reconstruction from noisy samples
Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-Hung Poon, Edgar Ramos
Pages: 302 - 311
Full text available: pdf formatPdf(410 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Restricted delaunay triangulations and normal cycle
David Cohen-Steiner, Jean-Marie Morvan
Pages: 312 - 321
Full text available: pdf formatPdf(378 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Estimating surface normals in noisy point cloud data
Niloy J. Mitra, An Nguyen
Pages: 322 - 328
Full text available: pdf formatPdf(456 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Shape dimension and intrinsic metric from samples of manifolds with high co-dimension
Joachim Giesen, Uli Wagner
Pages: 329 - 337
Full text available: pdf formatPdf(279 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Topology
    An optimal algorithm for the minimum edge cardinality cut surface problem
David E. Cardoze
Pages: 338 - 343
Full text available: pdf formatPdf(210 KB)
Additional Information:full citation, abstract, references, index terms
    Loops in reeb graphs of 2-manifolds
Kree Cole-McLaughlin, Herbert Edelsbrunner, John Harer, Vijay Natarajan, Valerio Pascucci
Pages: 344 - 350
Full text available: pdf formatPdf(331 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Molecular shape analysis based upon the morse-smale complex and the connolly function
F. Cazals, F. Chazal, T. Lewiner
Pages: 351 - 360
Full text available: pdf formatPdf(708 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Morse-smale complexes for piecewise linear 3-manifolds
Herbert Edelsbrunner, John Harer, Vijay Natarajan, Valerio Pascucci
Pages: 361 - 370
Full text available: pdf formatPdf(364 KB)
Additional Information:full citation, abstract, references, cited by, index terms
 
 
SESSION: Video and multimedia session
    The asteroid surveying problem and other puzzles
Timothy M. Chan, Alexander Golynski, Alejandro Lopez-Ortiz, Claude-Guy Quimper
Pages: 372 - 373
Full text available: pdf formatPdf(69 KB)
Additional Information:full citation, abstract, references, index terms
    VASCO: visualizing and animating spatial constructs and operations
Frantivsek Brabec, Hanan Samet, Cemal Yilmaz
Pages: 374 - 375
Full text available: pdf formatPdf(84 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Billboard clouds
Xavier Decoret, Fredo Durand, Francois X. Sillion
Pages: 376 - 376
Full text available: pdf formatPdf(40 KB)
Additional Information:full citation, references, index terms
    A 3-D visualization of kirkpatrick's planar point location algorithm
John Iacono
Pages: 377 - 377
Full text available: pdf formatPdf(49 KB)
Additional Information:full citation, abstract, references, index terms
    Morphing between shapes by using their straight skeletons
Gill Barequet, Evgeny Yakersberg
Pages: 378 - 379
Full text available: pdf formatPdf(119 KB)
Additional Information:full citation, references, index terms
    3DTreeDraw: a three dimensional tree drawing system
Tom Murtagh, Seok-Hee Hong
Pages: 380 - 381
Full text available: pdf formatPdf(648 KB)
Additional Information:full citation, abstract, references, index terms
    Online dispersion algorithms for swarms of robots
Tien-Ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sandor Fekete, Joseph S. B. Mitchell
Pages: 382 - 383
Full text available: pdf formatPdf(325 KB)
Additional Information:full citation, references, index terms
    Finding a curve in a map
Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan, Gunter Rote
Pages: 384 - 385
Full text available: pdf formatPdf(139 KB)
Additional Information:full citation, abstract, references, cited by, index terms
    Fast penetration depth estimation using rasterization hardware and hierarchical refinement
Young J. Kim, Miguel A. Otaduy, Ming C. Lin, Dinesh Manocha
Pages: 386 - 387
Full text available: pdf formatPdf(573 KB)
Additional Information:full citation, references, index terms
 


The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player