Author name cluster

John R. Gilbert

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

FOCS Conference 1990 Conference Paper

Provably Good Mesh Generation

Marshall W. Bern
David Eppstein
John R. Gilbert

Several versions of the problem of generating triangular meshes for finite-element methods are studied. It is shown how to triangulate a planar point set or a polygonally bounded domain with triangles of bounded aspect ratio, how to triangulate a planar point set with triangles having no obtuse angles, how to triangulate a point set in arbitrary dimension with simplices of bounded aspect ratio, and how to produce a linear-size Delaunay triangulation of a multidimensional point set by adding a linear number of extra points. All the triangulations have size within a constant factor of optimal and run in optimal time O(n log n+k) with input of size n and output of size k. No previous work on mesh generation simultaneously guarantees well-shaped elements and small total size. >

Details

STOC Conference 1979 Conference Paper

The Pebbling Problem is Complete in Polynomial Space

John R. Gilbert
Thomas Lengauer
Robert Endre Tarjan

We examine a pebbling problem which has been used to study the storage requirements of various models of computation. Sethi has shown this problem to be NP-hard and Lingas has shown a generalization to be P-space complete. We prove the original problem P-space complete by employing a modification of Lingas's proof. The pebbling problem is one of the few examples of a P-space complete problem not exhibiting any obvious quantifier alternation.

Details