Article
Full entry |
PDF
(1.0 MB)
Feedback
PDF
(1.0 MB)
Feedback
Keywords:
geometry; polygon; intersection; combinatorial complexity
geometry; polygon; intersection; combinatorial complexity
Summary:
We study the maximum possible number $f(k,l)$ of intersections of the boundaries of a simple $k$-gon with a simple $l$-gon in the plane for $k,l\ge 3$. To determine the number $f(k,l)$ is quite easy and known when $k$ or $l$ is even but still remains open for $k$ and $l$ both odd. We improve (for $k\le l$) the easy upper bound $kl-l$ to $kl-\left\lceil k/6\right\rceil-l$ and obtain exact bounds for $k=5$ $(f(5,l)=4l-2)$ in this case.
References:
[1] Aronov B., Sharir M.: The common exterior of convex polygons in the plane. Comput. Geom. 8 (3) (1997), 139-149. DOI 10.1016/S0925-7721(96)00004-1 | MR 1467119 | Zbl 0881.68122
[2] Dillencourt M.B., Mount D.M., Saalfeld A.J.: On The Maximum Number of Intersections of Two Polyhedra in 2 and 3 Dimensions. Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo, Ontario, August, 1993, pp.49-54.
[3] Efrat A., Sharir M.: On the complexity of the union of fat convex objects in the plane. Discrete Comput. Geom. 23 (2000), 171-189. DOI 10.1007/PL00009494 | MR 1739604 | Zbl 0944.68183
[4] Grünbaum B.: Selfintersections of polygons. Geombinatorics 8 (1998), 2 37-45. MR 1647013
[5] van Kreveld M.: On fat partitioning, fat covering and the union size of polygons. Comput. Geom. 9 (1994), 4 197-210. DOI 10.1016/S0925-7721(96)00016-8 | MR 1609598
[6] Matoušek J., Pach J., Sharir M., Sifrony S., Welzl E.: Fat triangles determine linearly many holes. SIAM J. Comput. 23 (1994), 1 154-169. DOI 10.1137/S009753979018330X | MR 1259000
[7] Pach J., Sharir M.: On the boundary of the union of planar convex sets. Discrete Comput. Geom. 3 (1999), 321-328. DOI 10.1007/PL00009424 | MR 1672968 | Zbl 0927.52001
Search
Partner of
