Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties

DOI10.1007/978-3-319-14974-5_9MaRDI QIDQ5174952zbMATH OpenOpenAlexFDO

Authors Ahmad Biniaz, Anil Maheshwari, Michiel Smid

Publication date 19 February 2015

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.5466

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We consider an extension of the triangular-distance Delaunay graphs (TD-Delaunay) on a set $P$ of points in the plane. In TD-Delaunay, the convex distance is defined by a fixed-oriented equilateral triangle $riangledown$, and there is an edge between two points in $P$ if and only if there is an empty homothet of $riangledown$ having the two points on its boundary. We consider higher-order triangular-distance Delaunay graphs, namely $k$-TD, which contains an edge between two points if the interior of the homothet of $riangledown$ having the two points on its boundary contains at most $k$ points of $P$. We consider the connectivity, Hamiltonicity and perfect-matching admissibility of $k$-TD. Finally we consider the problem of blocking the edges of $k$-TD.

Recommendations

• Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
• On structural and graph theoretic properties of higher order Delaunay graphs
• scientific article; zbMATH DE number 1670662
• Higher order Delaunay triangulations
• On the number of higher order Delaunay triangulations
• On the Number of Higher Order Delaunay Triangulations
• Optimal higher order Delaunay triangulations of polygons
• Optimal Higher Order Delaunay Triangulations of Polygons
• Towards a definition of higher order constrained Delaunay triangulations
• Constrained higher order Delaunay triangulations

Cited in

(12)

• Higher order Delaunay triangulations
• Dushnik-Miller dimension of TD-Delaunay complexes
• scientific article; zbMATH DE number 1670662 (Why is no real title available?)
• On structural and graph theoretic properties of higher order Delaunay graphs
• On the Number of Higher Order Delaunay Triangulations
• Fixed-orientation equilateral triangle matching of point sets
• Hamiltonicity for convex shape Delaunay and Gabriel graphs
• Some properties of k-Delaunay and k-Gabriel graphs
• Blocking Delaunay triangulations
• Fixed-orientation equilateral triangle matching of point sets
• Toughness and Delaunay triangulations
• Higher-order triangular-distance Delaunay graphs: graph-theoretical properties

This page was built for publication: Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties

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