🚀 go-pugleaf

Please find below an unsorted list of the papers accepted for presentation at
the 1993 ACM Symp on Computational Geometry. All authors will be informed
shortly.

Mark Overmars

----------------------------------------------------------------------------

			Accepted Papers
	1993 ACM Symposium on Computational Geometry


Convex distance functions in 3-space are different
C. Icking, R. Klein, N-M. Le, L. Ma

Computing a centerpoint of a finite planar set of points in linear time
S. Jadhav, A. Mukhopadhyay

An NC$^1$ Parallel 3D convex hull algorithm
N.M. Amato, F.P. Preparata

Optimal algorithms to detect null-homotopic cycles on 2-manifolds
T. Dey

Counting triangle crossings and halving planes
T. Dey, H. Edelsbrunner

An incremental algorithm for Betti numbers of simplicial complexes
C. Delfinado, H. Edelsbrunner

Algorithms for the union of balls in Euclidean space
H. Edelsbrunner

On lines missing polyhedral sets in 3-space
M. Pellegrini

Compatible tetrahedralizations
M. Bern

Worst-case bounds for subadditive geometric graphs
M. Bern, D. Eppstein

An expander-based approach to geometric optimization
M. Katz, M. Sharir

New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
D. Halperin, M. Sharir

A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon
R. Klein, A. Lingas

Generalized hidden surface removal
M. de Berg

Decision trees for geometric models
E. Arkin, H. Meijer, J. Mitchell, D. Rappaport, S. Skiena

Finding a minimum weight $K$-link path in graphs with Monge property and applications
A. Aggarwal, B. Schieber, T. Tokuyama

Approximating center points with and without linear programming
D. Eppstein, G. Miller, C. Sturtivant, S-H. Teng

A deterministic linear time algorithm for geometric separators and its applications
D. Eppstein, G. Miller, S-H. Teng

Shortest paths among obstacles in the plane
J. Mitchell

Area optimization of simple polygons
S. Fekete, W. Pulleyblank

Can visibility graphs be represented compactly?
P. Agarwal, N. Alon, B. Aronov, S. Suri

Long non-crossing configurations in the plane
N. Alon, S. Rajagopalan, S. Suri

The visibility complex
M. Pocchiola, G. Vegter

Efficient exact arithmetic for computational geometry
S. Fortune, C. van Wijk

An optimal algorithm for the two-guard problem
P. Heffernan

A generalization of Dehn-Sommerville relations to levels in arrangements
K. Mulmuley

Computing the discrepancy
D. Dobkin, D. Eppstein

An optimal algorithm for the $(\leq k)$-levels with applications to separation and transversal
H. Everett, J-M. Robert, M. van Kreveld

Complexity of translating a box in polyhedral 3-space
D. Halperin, C-K. Yap

Objects that cannot be taken apart with two hands
J. Snoeyink, J. Stolfi

Tentative prune-and-search for computing Voronoi vertices
D. Kirkpatrick, J. Snoeyink

A compaction algorithm for non-convex polygons and its application
Z. Li, V. Milenkovic

On the topological shape of planar Voronoi diagrams
A. Corbalan, M. Mazon, T. Recio, F. Santos

Helly theorems and generalized linear programming
N. Amenta

Geometric partitioning made easier, even in parallel
M. Goodrich

Dynamic ray shooting and shortest paths via balanced geodesic triangulations
M. Goodrich, R. Tamassia

Area-efficient upward tree drawings
A. Garg, M. Goodrich, R. Tamassia

Scalable parallel geometric algorithms for coarse grained multicomputers
F. Dehne, A. Fabri, A. Rau-Chaplin

Guaranteed-quality mesh generation for curved surfaces
P. Chew

Dominance range-query, the one-reporting case
T. Dub\'e

Optimal motion planning for a rod in the plane subject to velocity constraints
Y-B. Chen, D. Ierardi

Very sparse spanners in 3-dimensional Euclidean space
G. Das, P. Heffernan, G. Narasimhan

Some geometric applications of Dilworth's theorem
J. Pach, J. T\"or\H{o}csik