Numbers of Weights of Convex Quadrilaterals in Weighted Point Sets
Abstract
Let ℘n denote the family of sets of points in general position in the plane each of which is assigned a different number, called a weight, in {1,2,...,n}. For 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 Wk(P) the set of weights of convex k-gons with vertices in P∈℘n. Let fk(n) = minP∈℘n |Wk(P)|. It is known that n-5 ≤ f4(n) ≤ 2n-9 for n≥7. In this paper, we show that f4(n)≥ 4n/3-7.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.19184/ijc.2024.8.1.1
References
O. Aichholzer, F. Aurenhammer and H. Krasser, On the crossing number of complete graphs, in: SCG ’02: Proc. the 18th annual symp. on comput. geom. (2002), 19—24, https://doi.org/10.1145/513400.513403.
J. Balogh and G. Salazar, k-sets, convex quadrilaterals, and the rectilinear crossing number of Kn, Discrete Comput. Geom., 35 (2006), 671-–690, https://doi.org/10.1007/s00454-005-1227-6.
A. Brodsky, S. Durocher and E. Gethner, Toward the rectilinear crossing number of Kn: New drawings, upper bounds, and asymptotics, Discrete Math., 262 (2003), 59–77.
P. Erdös, Some old and new problems in combinatorial geometry, in: Convexity and Graph Theory, M. Rosenfeld et al., eds., Ann. Discrete Math., 20 (1984), 129–136.
P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math., 2 (1935), 463–470.
P. Erdös and G. Szekeres, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest, 3–4 (1960/61), 53–62.
R.K. Guy, Crossing numbers of graphs, Graph Theory and applications, Lecture Notes in Mathematics, 303 (1972), 111-–124.
F. Harary and A. Hill, On the number of crossings in a complete graph, Proc. Edinburgh Math. Soc., 13 (1962/63), 333–338.
J. D. Kalbfleisch, J. G. Kalbfleisch and R. G. Stanton, A combinatorial problem on convex ngons, Proc. Louisiana Conf. on Combinatorics, Graph Theory, and Computing, Baton Rouge, (1970), 180–188.
T. Sakai, Weights of convex quadrilaterals and empty triangles in weighted point sets, submitted.
G. Szekeres and L. Peters, Computer solution to the 17-point Erdös-Szekeres problem, The ANZIAM Journal, 48 (2006), 151–164, https://doi.org/10.1017/S144618110000300X.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.