Determine number of polygons given points in a planar domain

23 Views Asked by At

Suppose we have a 2D bounded domain $\Omega \in \mathbb{R}^2$ (for instance, $\Omega$ can be a square of side length $1$ centered at the origin), and we are given the coordinates of $n$ points $\{(x_i,y_i)\}_{1\leq i\leq n}$ inside $\Omega$ ($n \approx 100$ and those points can be thought to be roughly uniformly distributed inside the domain). Assume we have a fixed small threshold $s \approx 0.01$ such that an we join the points $(x_i,y_i)$ and $(x_j,y_j)$ with a line segment (i.e., an edge is formed) if and only if the distance between $(x_i,y_i)$ and $(x_j,y_j)$ are no more than $s$. I am wondering if it is possible determine (or asymptotically calculate) the number of $N$-polygons for each $N \geq 3$ (i.e., we are interested in the number of triangles, quadrilaterals, Pentagons,...etc) Of course, the result depends on the $n$ points given, so I am interested in having some algorithms to realize my goal.