Many empty triangles have a common edge

DOI10.1007/S00454-013-9506-0MaRDI QIDQ2391838zbMATH OpenOpenAlexFDO

Authors Jean-François Marckert, Matthias Reitzner, Imre Bárány

Publication date 5 August 2013

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

empty trianglesfinite point sets in the planerandom samples

Mathematics Subject Classification ID

Convex sets without dimension restrictions (aspects of convex geometry) (52A05) Random convex sets and integral geometry (aspects of convex geometry) (52A22) Geometric probability and stochastic geometry (60D05)

Abstract: Given a finite point set $X$ in the plane, the degree of a pair $x,ysubsetX$ is the number of empty triangles $t=convx,y,z$, where empty means $tcapX=x,y,z$. Define $degX$ as the maximal degree of a pair in $X$. Our main result is that if $X$ is a random sample of $n$ independent and uniform points from a fixed convex body, then $degXgecn/lnn$ in expectation.

Review text

Given a finite point set \(X\) in the plane, the degree of the pair \(\{x,y\} \subset X\) is the number of empty triangles \(t=\{x,y,z\}\), where empty means \(t\cap X = \{x,y,z\}\). Define \(\text{deg}(X)\) as the maximal degree of a pair in \(X\). The main result is that if \(X\) is a random sample of \(n\) independent and uniform points from a fixed convex body, then \(\text{deg}(X) \geq \frac{cn}{\ln(n)}\) in expectation.

Recommendations

• Moments of the maximal number of empty simplices of a random point set
• On degrees in random triangulations of point sets
• On degrees in random triangulations of point sets
• Random triangulations of planar points sets
• On edge-disjoint empty triangles of point sets

Cites work

• scientific article; zbMATH DE number 1149836 (Why is no real title available?)
• scientific article; zbMATH DE number 1786502 (Why is no real title available?)
• scientific article; zbMATH DE number 881170 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• Multidimensional Sorting
• Planar point sets with a small number of empty convex polygons
• Research Problems in Discrete Geometry

Cited in

(7)

• Moments of the maximal number of empty simplices of a random point set
• Limit theory for the Gilbert graph
• Many triangles with few edges
• A note on the number of general 4-holes in (perturbed) grids
• Stars of empty simplices
• Growth rate of the number of empty triangles in the plane
• Growth rates of the number of empty triangles and simplices

This page was built for publication: Many empty triangles have a common edge

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