- Title : Smallest Enclosing Circle Problems
- Speaker :Stefan Langerman(Universit ´e Libre de Bruxelles) - Date & Time : 12 December(Wed), 2012 (15p.m. - 16p.m.) - Place : Math Science building room 208 - Abstract : Given a set P of n points in the plane, we want to find the minimum enclosing circle of P whose center is constrained to lie on a given subset S of the plane, e.g., a set of points, a set of segments (or lines), or a simple polygon. For each situation we propose algorithms and matching lower bounds. Along the way, we find an W(n logm) lower bound in the algebraic computation tree model for the subset problem: Given two sets A and B of size m and n, is A a subset of B? Joint work with Luis Felipe Barba and Prosenjit Bose.
- Contact: Hee-Kap Ahn (heekap@postech.ac.kr, Tel. 279-2387 |
Activity >
