30th computational geometry day, friday Nov. 17

[Ricky Pollack]

			New York University
	     Courant Institute of Mathematical Sciences

		THIRTIETH COMPUTATIONAL GEOMETRY DAY

		      Friday, November 17, 2000
		     Room 109, Warren Weaver Hall
		  251 Mercer St., New York, NY 10012



0.00--10.30  Coffee (Warren Weaver Hall Lobby

10:30--11:15 Bernard Chazelle, Princeton University and NEC Research Institute
		The Discrepancy Method

11:30--12:15 Timothy Chan, Waterloo University
		On Levels in Arrangements of Curves

                12:30--2:00 Lunch
			
2:00--3:00    Open Problem Session
3:00--3:45  Micha Sharir, Courant Institute, NYU and Tel Aviv University 
		New Bounds for Incidences
4:00--5:00 Wine and Cheese Reception (13th floor lounge)

	For more information contact: Richard Pollack (212) 998-3167
                                                pollack at geometry.nyu.edu

*************************abstracts***************************************

		    The Discrepancy Method
			Bernard Chazelle
           Princeton University and NEC Research Institute

  The discrepancy method, which is the linkage between discrepancy 
  theory and peudorandomness, has been the most powerful tool for 
  understanding randomization as a computational resource. It has 
  also been used for proving lower bounds in circuit complexity and 
  communication complexity. I will review some of the milestones in 
  the story of the discrepancy method and I will discuss what it can 
  do and what it (probably) cannot do.


		On Levels in Arrangements of Curves
			Timothy Chan
		   University of Waterloo

We discuss a well-known problem: bounding the combinatorial complexity
of the $k$-level in an arrangement of $n$ curves in the plane.
Subquadratic upper bounds were known for lines (by Dey) and for graphs
of quadratic functions (by Tamaki and Tokuyama).  In this talk, we
extend these results and give the first nontrivial bound, near
$O(nk^{1-2/3^s})$, for curves that are graphs of polynomial functions
of any constant degree~$s$.

The proof is simple and relies on Tamaki and Tokuyama's theorem for
cutting pseudo-parabolas into pseudo-segments, as well as a new
observation for cutting pseudo-segments into pieces that can be
extended to pseudo-lines.

		
		   New Bounds for Incidences
			Micha Sharir
	  Courant Institute, NYU and Tel Aviv University

We present new upper bounds on the number of incidences between $m$ points
and $n$ circles in the plane. The known 10-year-old bound was
$O(m^{3/5}n^{4/5}+m+n)$. The new bounds are $O(m^{2/3}n^{2/3}+m)$
for $m\ge n^{3/2}$ and $O(m^{4/7}n^{17/21}+n)$ for $m\le n^{3/2}$.

The proof combines Sz\'ekely's technique, which is based on
crossing numbers of graphs, with Tamaki and Tokuyama's result on
cutting pseudo-parabolas, and with cuttings in dual space.

The talk will also review these tools and discuss several open
problems and challenges suggested by the new proof.

Finally, the new result of Chan, presented in this CG-Day,
facilitates the extension of the analysis
to obtain improved upper bounds for incidences involving points and
graphs of polynomial functions of any fixed maximum degree.

(Joint work with Boris Aronov.)


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/maillist.html.