Let \(\mathcal{P}_n\) denote the collection of sets of n points in general position in the plane each of which is assigned a different number, called a weight, in \(\{1,2,\dots , n\}\) . For \(P\in \mathcal{P}_n\) and a polygon Q with vertices in P, we define the weight of Q as the sum of the weights of its vertices and denote by \(W_4(P)\) the number of different weights of convex quadrilaterals with vertices in \(P\in \mathcal{P}_n\) . We immediately obtain \(|W_4(P)|\le 4n-15\) . We show that \(|W_4(P)|\ge n+o(n)\) for any \(P\in \mathcal{P}_n\) and that for \(n\ge 7\) , there exists \(P\in \mathcal{P}_n\) such that \(|W_4(P)|\le 2n-7\) . We consider a similar problem concerning weights of “empty” triangles. Let \(W_3^(P)\) denote the number of different weights of triangles that have vertices in P and contain no element of P in their interiors. We clearly have \(|W_3^(P)|\le 3n-8\) . We show that for \(n\ge 3\) , there exists \(P\in \mathcal{P}_n\) such that \(|W_3^(P)|\le 2n-5\) . We also show that \(|W_3^(P)|\ge \mathrm{\Omega }(\sqrt{n})\) for any \(P \in \mathcal{P}_n\) .

Weights of Convex Quadrilaterals and Empty Triangles in Weighted Point Sets

会议论文
发表日期：

2026年

查看全文

Toshinori Sakai

摘要

Let \(\mathcal{P}_n\) denote the collection of sets of n points in general position in the plane each of which is assigned a different number, called a weight, in \(\{1,2,\dots , n\}\) . For \(P\in \mathcal{P}_n\) and a polygon Q with vertices in P, we define the weight of Q as the sum of the weights of its vertices and denote by \(W_4(P)\) the number of different weights of convex quadrilaterals with vertices in \(P\in \mathcal{P}_n\) . We immediately obtain \(|W_4(P)|\le 4n-15\) . We show that \(|W_4(P)|\ge n+o(n)\) for any \(P\in \mathcal{P}_n\) and that for \(n\ge 7\) , there exists \(P\in \mathcal{P}_n\) such that \(|W_4(P)|\le 2n-7\) . We consider a similar problem concerning weights of “empty” triangles. Let \(W_3^*(P)\) denote the number of different weights of triangles that have vertices in P and contain no element of P in their interiors. We clearly have \(|W_3^*(P)|\le 3n-8\) . We show that for \(n\ge 3\) , there exists \(P\in \mathcal{P}_n\) such that \(|W_3^*(P)|\le 2n-5\) . We also show that \(|W_3^*(P)|\ge \mathrm{\Omega }(\sqrt{n})\) for any \(P \in \mathcal{P}_n\) .