CCCG'01: Accepted papers

Therese Biedl biedl at
Tue May 29 16:14:03 PDT 2001

The following 45 papers have been accepted to CCCG'01:

The Reflex-Free Hull
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Jack Snoeyink

The Point Set Order Type Data Base: A Collection of Applications and Results
Oswin Aichholzer, Hannes Krasser

On the Number of Triangulations every Planar Point Set must have
Oswin Aichholzer, Ferran Hurtado, Marc Noy

Algorithms for Bivariate Medians and a Fermat-Torricelli Problem for Lines
Greg Aloupis, Stefan Langerman, Michael Soss, Godfried Toussaint

Good Approximations for the Relative Neighbourhood Graph
Diogo Vieira Andrade, Luiz Henrique de Figueiredo

Line Voronoi diagram based interpolation and application to digital terrain
Francois Anton, Darka Mioc, Christopher M. Gold

Computational analysis of 4-8 meshes with application to surface
simplification using global error
Laurent Balmelli, Thomas Liebling, Martin Vetterli

A Simpler Circular Ray Shooting Algorithm
Ralph P. Boland, Jorge Urrutia

Finding the Largest Axis Aligned Rectangle in a Polygon in O(n log n) time
Ralph P. Boland, Jorge Urrutia

Guarding Lines and 2-Link Polygons is MAXSNP-Hard
Bjorn Broden, Mikael Hammar, Bengt J. Nilsson

Binary Space Partitioning Tree and Constructive Solid Geometry
Representations for Objects Bounded by Curved Surfaces
Suzanne F. Buchele, Angela C. Roles

On Algorithms for Simplicial Depth
Andrew Y. Cheng, Ming Ouyang

Translational Polygon Covering using Intersection Graphs
Karen Daniels, Rajasekhar Inkulu

The CCCG 2001 Logo
Erik D. Demaine, Martin L. Demaine, Anna Lubiw

Pushing Blocks is NP-Complete for Noncrossing Solution Paths
Erik D. Demaine, Michael Hoffmann

Short Interlocked Linkages
Erik D. Demaine, Stefan Langerman, Joseph O'Rourke

Reaching Folded States of a Rectangular Piece of Paper
Erik D. Demaine, Joseph S. B. Mitchell

The Shuffling Buffer
Olivier Devillers, Philippe Guigue

Separating Several Point Sets in the Plane
Olivier Devillers, Ferran Hurtado, Merce Mora, Carlos Seara

Decimating Samples for Mesh Simplification
Tamal K. Dey, Joachim Giesen, James Hudson

Matching Points to a Convex Polygonal Boundary
Matthew T. Dickerson, Michael T. Goodrich

The Convex Hull in a New Model of Computation
Abbas Edalat, Andre Lieutier, Elham Kashefi

Complete Combinatorial Generation of Small Point Configurations and
Hyperplane Arrangements
Lukas Finschi, Komei Fukuda

Computing the Width of a Point Set in 3-Space
Bernd Gaertner, Thomas Herrmann

Approximating the Shortest Path in Line Arrangements
David W. Hart

Segment endpoint visibility graphs are Hamiltonian
Michael Hoffmann, Csaba D. Toth

Local Optimization of Triangular Surface Meshes for General Quadrics in Lp
Jerzy W. Jaromczyk, Yang Wang

Tight Degree Bounds for Pseudo-triangulations of Points
Lutz Kettner, David Kirkpatrick, Bettina Speckmann

Listing All Connected Plane Triangulation
Zhangjian Li, Shin-ichi Nakano

Parallel Searching on a Lattice
Alejandro Lopez-Ortiz, Graeme Sweet

Andrea Mantler, Jack Snoeyink

On the Topology of the Level Sets of a Scalar Field
Valerio Pascucci

Voronoi Diagrams in Projective Geometry and Sweep Circle Algorithms for
Constructing Circle-based Voronoi Diagrams'
Axel Pavillet

Counting triangulations and pseudo-triangulations of wheels
Dana Randall, Guenter Rote, Francisco Santos, Jack Snoeyink

Narrowing Light Rays with Mirrors
Joseph O'Rourke, Octavia Petrovici

Partitioning Orthogonal Polygons into Fat Rectangles
Joseph O'Rourke, Irena Pashchenko, Geetika Tewari

Heuristics for placing non-orthogonal axial lines to cross the adjacencies
between orthogonal rectangles
Ian Sanders, Leigh-Ann Kenny

Nearest neighbor search through function minimization
Chang Shu, Michael Greenspan, Guy Godin

The Arithmetic Precision of Ray-Polygon Intersection Testing
Jack Snoeyink

Testing Extendability for Partial Chirotopes is NP-complete
Falk Tschirschnitz

Tiling 3D Euclidean Space with Acute Tetrahedra
Alper Ungor

Tutte's Barycenter Method applied to Isotopies
Eric Colin de Verdiere, Michel Pocchiola, Gert Vegter

Yet Another Look at Fractional Cascading: B-graphs with Application to Point
Chee Yap, Yunyue Zhu

Geometric Permutations of Balls with Bounded Size Disparity
Yunhong Zhou, Subhash Suri

Turing Computability of (Non-)Linear Optimization
Martin Ziegler, Vasco Brattka

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list