More on Generalized Jewels and the Point Placement Problem
Md. Shafiul Alam and Asish Mukhopadhyay
Vol. 18, no. 1, pp. 133-173, 2014. Regular paper.
Abstract The point placement problem is to determine the positions of a set of n distinct points, P = {p1, p2, p3, …, pn}, 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 paper we show how to construct in 2 rounds a line-rigid point placement graph of size 4n/3 + O(1) from certain small-sized graphs called 6:6 jewels. This improves an earlier result that used cycle-graphs on 5 vertices. More significantly, we improve the lower bound on 2-round algorithms from 17n/16 to 12n/11.
Submitted: July 2012.
Reviewed: February 2013.
Revised: May 2013.
Accepted: January 2014.
Final: February 2014.
Published: February 2014.
Communicated by Xin He
article (PDF)