| Title:
|
On the number of intersections of two polygons (English) |
| Author:
|
Černý, Jakub |
| Author:
|
Kára, Jan |
| Author:
|
Král', Daniel |
| Author:
|
Podbrdský, Pavel |
| Author:
|
Sotáková, Miroslava |
| Author:
|
Šámal, Robert |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
44 |
| Issue:
|
2 |
| Year:
|
2003 |
| Pages:
|
217-228 |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
geometry |
| Keyword:
|
polygon |
| Keyword:
|
intersection |
| Keyword:
|
combinatorial complexity |
| MSC:
|
52C10 |
| MSC:
|
52C45 |
| idZBL:
|
Zbl 1099.52004 |
| idMR:
|
MR2026159 |
| . |
| Date available:
|
2009-01-08T19:28:53Z |
| Last updated:
|
2020-02-20 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119381 |
| . |
| Reference:
|
[1] Aronov B., Sharir M.: The common exterior of convex polygons in the plane.Comput. Geom. 8 (3) (1997), 139-149. Zbl 0881.68122, MR 1467119, 10.1016/S0925-7721(96)00004-1 |
| Reference:
|
[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. |
| Reference:
|
[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. Zbl 0944.68183, MR 1739604, 10.1007/PL00009494 |
| Reference:
|
[4] Grünbaum B.: Selfintersections of polygons.Geombinatorics 8 (1998), 2 37-45. MR 1647013 |
| Reference:
|
[5] van Kreveld M.: On fat partitioning, fat covering and the union size of polygons.Comput. Geom. 9 (1994), 4 197-210. MR 1609598, 10.1016/S0925-7721(96)00016-8 |
| Reference:
|
[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. MR 1259000, 10.1137/S009753979018330X |
| Reference:
|
[7] Pach J., Sharir M.: On the boundary of the union of planar convex sets.Discrete Comput. Geom. 3 (1999), 321-328. Zbl 0927.52001, MR 1672968, 10.1007/PL00009424 |
| . |
