More on Generalized Jewels and the Point Placement Problem

Authors

  • Md. Shafiul Alam
  • Asish Mukhopadhyay

DOI:

https://doi.org/10.7155/jgaa.00317

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.

Downloads

Download data is not yet available.

Downloads

Published

2014-01-01

How to Cite

Alam, M. S., & Mukhopadhyay, A. (2014). More on Generalized Jewels and the Point Placement Problem. Journal of Graph Algorithms and Applications, 18(1), 133–173. https://doi.org/10.7155/jgaa.00317

Issue

Section

Articles

Categories