From: pollack@GEOMETRY.CIMS.NYU.EDU ("", Ricky Pollack)
Newsgroups: comp.theory
Subject: twentieth computational geometry day
Date: 2 Oct 92 22:18:31 GMT
Reply-To: Theory-A - TheoryNet World-Wide Events <THEORY-A%NDSUVM1.BITNET@cmsa.Berkeley.EDU>,
        "(Ricky Pollack)" <pollack@geometry.cims.nyu.edu>


                Twentieth COMPUTATIONAL GEOMETRY DAY
                       Friday, November 13, 1991
                          New York University
              Courant Institute of Mathematical Sciences
                    Room 109,  Warren Weaver Hall
                  251 Mercer St., New York, NY 10012



                10.00-10.30 - Coffee (13th floor lounge)
        10:30-11:15 Pankaj Agarwal, Duke University
		    Half-Space Reporting, Ray Shooting, and
			Geometric Optimization

        11:30-12:15 Jeff Kahn, Rutgers University
                   Geometric Aspects of Sorting Partially Ordered Sets

        12:30-2:00 Lunch


        2:00-3:00    Open Problem Session

        3:00-3:45  Laszlo Lovasz, Princeton University
		   Decision Trees and Moebius Functions


        4:00-5:00 Wine and Cheese Reception (13th floor lounge)


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


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

		    Pankaj Agarwal, Duke University
	Half-space reporting, ray shooting, and geometric optimization

We describe how half-space range searching can be used to do ray shooting
in a convex polyhedron, which in turn yields fast procedures for several
proximity problems.  We also describe dynamic data structures for half-space
range reporting. Based on these structures we obtain dynamic algorithms for
various geometric optimization problems.




              		Jeff Kahn, Rutgers University
	        Geometric Aspects of Sorting Partially Ordered S

By {\em sorting} a partially ordered set (poset) $P$ we mean selecting one
from among the possible linear extensions (i.e. linear orders extending $P$)
by means of comparisons of pairs of elements.  This is also known as
{\em sorting under partial information}.

If $e(P)$ is the number of linear extensions of $P$, then sorting $P$ clearly
requires at least $\log(e(P))$ comparisons.  This is the {\em information
theory lower bound} or ITLB (logs are base 2).  This raises two issues:  how
many comparisons are {\em actually} required to sort, and how hard is it to
find the comparisons?

Curiously, most advances on the problem have required application of geometric
tools (Brunn-Minkowski, Aleksandrov-Fenchel, ellipsoid algorithm) to one of
several polytopes associated with the poset.  In this talk we survey some of
these developments, for example: Fredman's 1976 bound of $\log(e(P))+2|P|$ on
the number of comparisons needed to sort $P$; the $O(\log(e(P))$ bound of M.
Saks and the speaker from 1984, and subsequent developments on the existence
of ``extension-splitting" comparisons; and recent work of J.H. Kim and the
speaker, using graph entropy and the ellipsoid algorithm to sort in
$O(\log(e(P))$ comparisons and {\em find the comparisons in polynomial time}.

Though, with the last-mentioned result, the algorithmic situation is now
fairly satisfactorily resolved (that is, except for constants and exponents of
polynomials), most of the best known {\em non}algorithmic problems in the area
remain open.


			    Laslo Lovasz
			Princeton University

Given $n$ real numbers, we want to determine whether any $k$ of them are
equal. As a basic step, we are allowed to test whether a given linear function
of the numbers is positive, negative, or 0.  The main result, obtained jointly
with A. Bjorner and A. Yao, is that one need at least $cn \log(2n/k)$ tests in
the worst case.  This bound can be achieved up to a constant factor.

The method of proof is a topological extension of the ``component counting''
lower bound technique. One can show that the number of tests is, in the worst
case, at least the logarithm of the Euler characeristic of an associated
polyhedron. This Euler characteristic can be found using the theory of
M\"obius functions.

Extensions of these results to non-linear decision trees by Yao, and to
connections between linear decision trees and Betti numbers by Bjorner and
Lov\'asz, are also described.
Newsgroups: comp.theory,sci.math