Combinatorics, Probability and Computing

Table of Contents - 1998 - Volume 7, Issue 01  


On the Number of Incidences Between Points and Curves

JÁNOS PACH a1 1 and MICHA SHARIR a2 1
a1 Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA; and Department of Computer Science, City College, CUNY, New York, NY, USA (e-mail: pach@cims6.cims.nyu.edu)
a2 Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA; and School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: sharir@math.tau.ac.il)

Abstract

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.

(Received April 26 1996)
(Revised February 10 1997)


Footnotes

1 Work on this paper by both authors has been supported by NSF Grant CCR-94-24398. Work by János Pach was also supported by Grant OTKA-T-020914 and by a CUNY Research Award. Work by Micha Sharir was also supported by NSF Grant CCR-93-11127, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.