Seminar by Ashish Mukhopadhyay
Point Placement on a line
Ashish Mukhopadhyay
University of Windsor, Canada
Date: Monday, August 20th, 2010
Time: 4:00 PM
Venue: CS101.Abstract:
The point placement problem is to determine the positions of a set of n distinct points, P = {p_1,p_2, ..., p_n}, on a line uniquely, up to translation and reflection, from the fewest possible distance queries between pairs of points. Each distance query corresponds to an edge in a graph, called point placement graph (ppg), whose vertex set is P. The uniqueness requirement of the placement translates to line-rigidity of the ppg. In this talk we show how to construct in two rounds a line-rigid ppg of size 4n/3 + O(1) from small components called 6:6 jewels. This improves a previously reported result of 4n/3 + O(sqrt(n)) based on 5-cycles. We also improve the lower bound on 2-round algorithms from 17n/16 to 12n/11
About the speaker:
Ashish Mukhopadhyay's research interest is broadly in the area of Geometric Algorithms. He was a faculty member of CSE department, IIT Kanpur, during 1983-1998. More information about him is at http://cs.uwindsor.ca/~asishm/.