Title:
The Cover Contact Graph of Discs Touching a Line
Date:
Thursday, August 2, 2012 @ 1:00pm
Location:
E2-304 EITC Building, University of Manitoba Fort Garry Campus
Speaker:
Matthew Skala, University of Manitoba
Abstract:
We answer a question of Atienza et al. by showing that the circular
CCG+ problem is NP-complete. If we cover a set of objects on the plane
with discs whose interiors are pairwise disjoint, then we can form a
cover contact graph (CCG) that records which of the covering discs
touch at their boundaries. When the input objects are themselves
discs, and both input and covering discs are constrained to be
touching and above the x-axis, then the circular CCG+ problem is to
decide the existence of a covering with a connected CCG. We also
define an approximate version of this problem by allowing a small
overlap between covering discs, and give an algorithm that in
polynomial time finds an approximate solution for any yes-instance of
the exact problem.
Joint work with Stephane Durocher, Saeed Mehrabi, and Mohammad Abdul Wahid.
Cost:
This will be a free event.
Contact:
If you would like additional information or if you might be interested in presenting a seminar, please contact Stephane Durocher or the Department of Computer Science.
