On the Number of Incidences Between Points and Curves

JÁNOS PACH; MICHA SHARIR

doi:10.1017/S0963548397003192

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We apply an idea of Székely to prove a general upper bound on the number of incidences between a set of m points and a set of n ‘well-behaved’ curves in the plane.

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Pach, János and Tóth, Géza 1997. Graph Drawing. Vol. 1190, Issue. , p. 345.

Pach, J�nos and T�th, G�za 1997. Graphs drawn with few crossings per edge. Combinatorica, Vol. 17, Issue. 3, p. 427.

Pach, János Spencer, Joel and Tóth, Géza 1999. New bounds on crossing numbers. p. 124.

Pach, J. Spencer, J. and Tóth, G. 2000. New Bounds on Crossing Numbers. Discrete & Computational Geometry, Vol. 24, Issue. 4, p. 623.

Pach, János 2000. Discrete and Computational Geometry. Vol. 1763, Issue. , p. 267.

Elekes, György and Rónyai, Lajos 2000. A Combinatorial Problem on Polynomials and Rational Functions. Journal of Combinatorial Theory, Series A, Vol. 89, Issue. 1, p. 1.

Agarwal, Pankaj K. and Sharir, Micha 2000. Handbook of Computational Geometry. p. 49.

Solymosi, J. and Toth, Csaba D. 2001. On the distinct distances determined by a planar point set. p. 29.

Aronov, Boris Koltun, Vladlen and Sharir, Micha 2002. Incidences between points and circles in three and higher dimensions. p. 116.

Agarwal, Pankaj K. Aronov, Boris and Sharir, Micha 2003. Discrete and Computational Geometry. Vol. 25, Issue. , p. 1.

Elekes, G. 2003. On the number of distinct radii of circles determined by triples and on parameters of other curves. Studia Scientiarum Mathematicarum Hungarica, Vol. 40, Issue. 1-2, p. 195.

Székely, László A. 2004. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Mathematics, Vol. 276, Issue. 1-3, p. 331.

Pach, János Radoicić, Radoš Tardos, Gábor and Tóth, Géza 2004. Improving the crossing lemma by finding more crossings in sparse graphs. p. 68.

2005. Research Problems in Discrete Geometry. p. 289.

Pach, János and Sharir, Micha 2005. Graph Theory, Combinatorics and Algorithms. Vol. 34, Issue. , p. 267.

SOLYMOSI, JÓZSEF and TÓTH, CSABA D. 2008. On a Question of Bourgain about Geometric Incidences. Combinatorics, Probability and Computing, Vol. 17, Issue. 4, p. 619.

Fox, Jacob Pach, János and Tóth, Csaba D. 2008. Graph Drawing. Vol. 4875, Issue. , p. 13.

Dujmovic, Vida Kawarabayashi, Ken-ichi Mohar, Bojan and Wood, David R. 2008. Improved upper bounds on the crossing number. p. 375.

Pach, János Solymosi, József and Tardos, Gábor 2010. Crossing numbers of imbalanced graphs. Journal of Graph Theory, Vol. 64, Issue. 1, p. 12.

Fox, Jacob Pach, János and Tóth, Csaba D. 2010. A bipartite strengthening of the Crossing Lemma. Journal of Combinatorial Theory, Series B, Vol. 100, Issue. 1, p. 23.

Download full list

Article contents

On the Number of Incidences Between Points and Curves

Abstract

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests