art@CS.SFU.CA (02/13/90)
The next WOBCATS meeting will be held in room 9896 of the new Applied Sciences
Building at Simon Fraser University in beautiful Burnaby, B. C. on Monday,
February 26, 1990. The speakers will be Chris Wilson (U. of Oregon),
Deborah Joseph (visiting U. of Washington) and Maria Klawe (U. of British
Columbia).
See abstracts below.
Schedule
11:00 coffee, juice, muffins
11:30 talk by Maria Klawe
12:30 lunch
1:30 talk by Chris Wilson
2:30 break
3:15 talk by Deborah Joseph
4:15 adjourn to University Club for socialism
The Applied Sciences Building is located at the southeastern edge of the
campus and is near a visitors parking lot. From the TransCanada Highway
(Hwy 1), take the Cariboo exit and proceed on Gaglardi Way to SFU.
There is an information booth at the main entrance. The folks there can
direct you to visitors parking and to our building.
If you are coming from far away and need accommodation, we recommend the
Best Western Coquitlam Motor Inn ((604)-931-9011) with rates in the $80-
$100 range. (for example, two beds/two persons is $89.00) The Inn is about
ten minutes from SFU by car and also close to an SFU-bound bus. (You can't
get much closer since we are on top of a (small) mountain.) Please mention
the School of Computing Science at SFU when you call for a reservation.
If you wish to stay in downtown Vancouver, there are lots of hotels but you
are on your own.
If you are flying to Vancouver, SFU (and the Coquitlam Best Western) are
about 45 minutes (by car) from the airport if there is no traffic (or snow).
Please let me know how many people from your institution will be attending
(no later than February 19, please) so that we can arrange lunch.
AND NOW, THE ABSTRACTS:
*****************************************************************************
An O(n log log n) Algorithm for Polygon Triangulation with Simple
Data-Structures
by Maria M. Klawe
Partitioning the interior of a polygon into triangles by adding
non-intersecting diagonals of the polygon has widespread applications
in computer graphics, pattern recognition, and computational morphology,
as well as playing a fundamental role as a building block in the
solution of many problems in computational geometry. In this talk,
we present a new O(n log log n) time algorithm for triangulating simple
n-vertex polygons, which avoids the use of complicated data-structures.
The major new technique employed is a linear time algorithm for obtaining
the horizontal visibility partition of a subchain of a polygonal chain,
from the horizontal visibility partition of the entire chain. This
technique has other interesting applications including a linear time
algorithm to convert a Steiner triangulation of a polygon to a true
triangulation. (The work presented is joint work with David Kirkpatrick
and Bob Tarjan.)
*****************************************************************************
Circuits with Limited Negations
by Chris Wilson
There recently have been some very nice results on the limitations of the
power of certain types of monotone circuits. These results would answer
fundamental questions in complexity theory if they could be carried over
to the non-monotone case. A question we address is an intermediate one:
what is the power of circuits with a limitation on the number of negation
gates? How much can this number be limited without changing the power of
the circuit class? A basic theorem of Markov is that the minimum number
of negation gates needed for a circuit to compute any Boolean function on
n variables is log n, but these circuits have no restriction on their size
or depth. We show that this result holds down to NC^1: log n negations are
necessary and sufficient to compute everything within NC^1. On the contrary,
constant depth threshold circuits (TC^0) and constant depth circuits (AC^0)
behave quite differently. For each of these classes we derive essentially
matching upper and lower bounds on the number of negations which preserve
the class. (This talk describes joint work with Miklos Santha.)
*****************************************************************************
The Complexity of Finding Minimum Nested Polyhedra
by Deborah Joseph
In this talk we consider the following problem. Given two nested polyhedra,
P and Q, with Q nested in P, find a third polyhedron R that encloses
Q and is contained in P such that the number of faces on R is minimal.
This problem was posed by Klee and a polynomial time algorithm was given
by Aggarwal, Booth, O'Rourke, Suri and Yap for the 2-dimensional problem.
We show that the 3-dimensional problem is NP-hard. (This talk describes
joint work with Gautam Das.)
*****************************************************************************
For more information, please contact:
Art Liestman (604)-291-4197 (art@cs.sfu.ca) (FAX (604)-291-3045)