A non-Hamiltonian, nondegenerate Delaunay triangulation

DOI10.1016/0020-0190(87)90124-4zbMATH Open0653.68073OpenAlexW1996236086MaRDI QIDQ1108041FDOQ1108041

Authors: 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

computational geometryDelaunay triangulationVoronoi diagramHamiltonian graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Traveling salesman cycles are not always subgraphs of Voronoi duals

Cited In (14)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108041)