Fixed-orientation equilateral triangle matching of point sets

DOI10.1007/978-3-642-36065-7_4MaRDI QIDQ4915875zbMATH OpenOpenAlexFDO

Authors Jasine Babu, Ahmad Biniaz, Anil Maheshwari, Michiel Smid

Publication date 12 April 2013

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

Delaunay graphsgeometric graphsmatchings

Mathematics Subject Classification ID

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

Abstract: Given a point set $P$ and a class $mathcalC$ of geometric objects, $G_{m}athcalC(P)$ is a geometric graph with vertex set $P$ such that any two vertices $p$ and $q$ are adjacent if and only if there is some $CinmathcalC$ containing both $p$ and $q$ but no other points from $P$. We study $$ graphs where $$ is the class of downward equilateral triangles (ie. equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-$Thet{a}_6$ graphs and TD-Delaunay graphs. The main result in our paper is that for point sets $P$ in general position, $$ always contains a matching of size at least $lceilfracn-23ceil$ and this bound cannot be improved above $lceilfracn-13ceil$. We also give some structural properties of $G_{davidsstar}(P)$ graphs, where $davidsstar$ is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of $G_{davidsstar}(P)$ is simply a path. Through the equivalence of $G_{davidsstar}(P)$ graphs with $Thet{a}_6$ graphs, we also derive that any $Thet{a}_6$ graph can have at most $5n-11$ edges, for point sets in general position.

Recommendations

• Fixed-orientation equilateral triangle matching of point sets
• Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
• Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties
• Strong matching of points with geometric shapes
• Triangulations intersect nicely

Cited in

(4)

• Strong matching of points with geometric shapes
• Maximum matchings and minimum blocking sets in \(\varTheta_6\)-graphs
• Selection lemmas for various geometric objects
• Fixed-orientation equilateral triangle matching of point sets

This page was built for publication: Fixed-orientation equilateral triangle matching of point sets

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