On the number of intersections of two polygons
Jakub Černý; Jan Kára; Daniel Kráľ; Pavel Podbrdský; Miroslava Sotáková; Robert Šámal
Commentationes Mathematicae Universitatis Carolinae (2003)
- Volume: 44, Issue: 2, page 217-228
- ISSN: 0010-2628
Access Full Article
top
Abstract
topHow to cite
topČerný, Jakub, et al. "On the number of intersections of two polygons." Commentationes Mathematicae Universitatis Carolinae 44.2 (2003): 217-228. <http://eudml.org/doc/249189>.
@article{Černý2003,
abstract = {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.},
author = {Černý, Jakub, Kára, Jan, Kráľ, Daniel, Podbrdský, Pavel, Sotáková, Miroslava, Šámal, Robert},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {geometry; polygon; intersection; combinatorial complexity; combinatorial complexity},
language = {eng},
number = {2},
pages = {217-228},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {On the number of intersections of two polygons},
url = {http://eudml.org/doc/249189},
volume = {44},
year = {2003},
}
TY - JOUR
AU - Černý, Jakub
AU - Kára, Jan
AU - Kráľ, Daniel
AU - Podbrdský, Pavel
AU - Sotáková, Miroslava
AU - Šámal, Robert
TI - On the number of intersections of two polygons
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2003
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 44
IS - 2
SP - 217
EP - 228
AB - 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.
LA - eng
KW - geometry; polygon; intersection; combinatorial complexity; combinatorial complexity
UR - http://eudml.org/doc/249189
ER -
References
top- Aronov B., Sharir M., 10.1016/S0925-7721(96)00004-1, Comput. Geom. 8 (3) (1997), 139-149. (1997) Zbl0881.68122MR1467119DOI10.1016/S0925-7721(96)00004-1
- 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.
- Efrat A., Sharir M., 10.1007/PL00009494, Discrete Comput. Geom. 23 (2000), 171-189. (2000) Zbl0944.68183MR1739604DOI10.1007/PL00009494
- Grünbaum B., Selfintersections of polygons, Geombinatorics 8 (1998), 2 37-45. (1998) MR1647013
- van Kreveld M., 10.1016/S0925-7721(96)00016-8, Comput. Geom. 9 (1994), 4 197-210. (1994) MR1609598DOI10.1016/S0925-7721(96)00016-8
- Matoušek J., Pach J., Sharir M., Sifrony S., Welzl E., 10.1137/S009753979018330X, SIAM J. Comput. 23 (1994), 1 154-169. (1994) MR1259000DOI10.1137/S009753979018330X
- Pach J., Sharir M., 10.1007/PL00009424, Discrete Comput. Geom. 3 (1999), 321-328. (1999) Zbl0927.52001MR1672968DOI10.1007/PL00009424
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.