A non-Hamiltonian, nondegenerate Delaunay triangulation

DOI10.1016/0020-0190(87)90124-4zbMath0653.68073OpenAlexW1996236086MaRDI QIDQ1108041

Michael B. Dillencourt

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90124-4

zbMATH Keywords

Hamiltonian graphVoronoi diagramcomputational geometryDelaunay triangulation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Other problems of combinatorial convexity (52A37)

Related Items

On certain Hamiltonian inner triangulations ⋮ PROXIMITY GRAPHS: E, δ, Δ, χ AND ω ⋮ 2-change for k-connected networks ⋮ Good triangulations yield good tours ⋮ Finding Hamiltonian cycles in Delaunay triangulations is NP-complete ⋮ An upper bound on the shortness exponent of inscribable polytopes ⋮ Higher-order triangular-distance Delaunay graphs: graph-theoretical properties ⋮ Connectivity of plane triangulations ⋮ The \(\gamma\)-neighborhood graph ⋮ Angle-restricted tours in the plane. ⋮ Matching points with squares ⋮ Hamiltonicity for convex shape Delaunay and Gabriel graphs ⋮ Toughness and Delaunay triangulations ⋮ 10-Gabriel graphs are Hamiltonian

Cites Work

• Traveling salesman cycles are not always subgraphs of Voronoi duals
• Unnamed Item

This page was built for publication: A non-Hamiltonian, nondegenerate Delaunay triangulation