Celebratio Mathematica — Hass — Complete Bibliography

Complete Bibliography

Works connected to János Pach

Filter the Bibliography List

year	title	people

			clear

J. Hass and J. C. Lagarias: “The minimal number of triangles needed to span a polygon embedded in $R^{d}$ ,” pp. 509–526 in Discrete and computational geometry: The Goodman–Pollack Festschrift. Edited by B. Aronov, S. Basu, J. Pach, and M. Sharir. Algorithms and Combinatorics 25. Springer (Berlin), 2003. MR 2038489 Zbl 1103.52013 incollection

Given a closed polygon $ P $ having $ n $ edges, embedded in $ \mathbb{R}^d $, we give upper and lower bounds for the minimal number of triangles $ t $ needed to form a triangulated PL surface embedded in $ \mathbb{R}^d $ having $ P $ as its geometric boundary. More generally we obtain such bounds for a triangulated (locally flat) PL surface having $ P $ as its boundary which is immersed in $ \mathbb{R}^d $ and whose interior is disjoint from $ P $. The most interesting case is dimension 3, where the polygon may be knotted. We use the Seifert surface construction to show that for any polygon embedded in $ \mathbb{R}^3 $ there exists an embedded orientable triangulated PL surface having at most $ 7n^2 $ triangles, whose boundary is a subdivision of $ P $. We complement this with a construction of families of polygons with $ n $ vertices for which any such embedded surface requires at least $ \frac{1}{2}n^2 - O(n) $ triangles. We also exhibit families of polygons in $ \mathbb{R}^3 $ for which $ \Omega(n^2) $ triangles are required in any immersed PL surface of the above kind. In contrast, in dimension 2 and in dimensions $ d\geq 5 $ there always exists an embedded locally flat PL disk having $ P $ as boundary that contains at most $ n $ triangles. In dimension 4 there always exists an immersed locally flat PL disk of the above kind that contains at most $ 3n $ triangles. An unresolved case is that of embedded PL surfaces in dimension 4, where we establish only an $ O(n^2) $ upper bound. These results can be viewed as providing qualitative discrete analogues of the isoperimetric inequality for piecewise linear (PL) manifolds. In dimension 3 they imply that the (asymptotic) discrete isoperimetric constant lies between $ 1/2 $ and 7.

János Pach	Related
Jacob E. Goodman	Related
Richard Pollack	Related