Home > CSC-OpenAccess Library > Manuscript Information

This is an Open Access publication published under CSC-OpenAccess Policy.

Point Placement Algorithms: An Experimental Study

Asish Mukhopadhyay, Pijus K. Sarker, Kishore Kumar V. Kannnan

Pages - 1 - 13 | Revised - 31-05-2016 | Published - 30-06-2016

MORE INFORMATION

KEYWORDS

Computational Geometry, Point-placement, Turnpike Problem, Experimental Algorithms.

ABSTRACT

The point location problem is to determine the position of n distinct points on a line, up to translation
and reflection by the fewest possible pairwise (adversarial) distance queries. In this paper we report
on an experimental study of a number of deterministic point placement algorithms and an
incremental randomized algorithm, with the goal of obtaining a greater insight into the practical
utility of these algorithms, particularly of the randomized one.

1 | Google Scholar |

2 | CiteSeerX |

3 | Scribd |

4 | SlideShare |

5 | PdfSR |

1 | A. Mukhopadhyay, S. Rao, S. Pardeshi and S. Gundlapalli. "Linear Layouts of weakly triangulated graphs". Workshop on Algorithms and Computation, Chennai, 2014. |

2 | J. Saxe. "Embeddability of weighted graphs in k-space is strongly NP-hard". 17th Allerton Conference on Communication, Control and Computing, 1979. |

3 | G. Young and A. Householder. "Disussion of a set of points in terms of their mutula distances". Pychometrika, vol. 3, no. 1, pp. 19-22, 1938. |

4 | L. Blumenthal. Thory and applications of distance geometry, 2nd edition. New York: Chelsea, 1970. |

5 | A. Y. Alfakih, A. Khandani and H. Wolkowicz. "Solving euclidean matrix distance completion problems using semi-definite programming". Comput. Optim. Applications, vol. 12, no. 1-3, pp. 13-30, 1999. |

6 | M. Laurent. "Matrix completion problems". Encyclopedia of Optimization, Second Edition, 2009, pp. 1967-1975. |

7 | M. Bakonyi and C. Johnson. "The euclidean matrix distance completion problem". SIAM J. Matrix Anal. Appl., vol. 16, no. 2, pp. 646-654, 1995. |

8 | P. Damaschke. "Point placement on the line by distance data". Discrete Applied Mathematics, vol. 127, no. 1, p. 53–62, 2003. |

9 | S. Skiena, W. Smith and P. Lemke. "Reconstructing sets from interpoint distances". In Sixth Annual ACM Symposium on Computational Geometry, New York, 1990. |

10 | A. Daurat, Y. Gérard and M. Nivat. "The chords’ problem". Theor. Comput. Sci., vol. 282, no. 2, p. 319–336, 2002. |

11 | H. Smith and K. Wilcox. "A restriction enzyme from hemophilus influenzae. i. purification and general properties". Journal of Molecular Biology, vol. 51, p. 379–391, 1970. |

12 | J. Redstone and W. W. L. Ruzzo. "Algorithms for a simple point placement problem". In CIAC'00:Proceedings of the 4th Italian Conference on Algorithms and Complexity, London, UK, 2000. |

13 | B. Mumey. "Probe location in the presence of errors: a problem from DNA mapping". Discrete Applied Mathematics, vol. 104, no. 1-3, pp. 187-201, 2000. |

14 | P. Damaschke. "Randomized vs. deterministic distance query strategies for point location on the line". Discrete Applied Mathematics, vol. 154, no. 3, pp. 478-484, 2006. |

15 | F. Chin, H. Leung, W.-K. Sung and S.-M. Yiu. "The point placement problem on a line - improved bounds for pairwise distance queries". In Proceedings of the Workshop on Algorithms in Bioinformatics, 2007. |

16 | M. Alam and A. A. Mukhopadhyay. "More on generalized jewels and the point placement problem". J. Graph Algorithms Appl., vol. 18, no. 1, pp. 133-173, 2014. |

17 | M. Alam and A. Mukhopadhyay. "Three paths to point placement". In Proceedings of the Conference on Algorithms and Discrete Applied Mathematics, 2015. |

18 | R. Motawani and P. Raghavan. Randomized Algorithms. New York, NY: Cambridge University Press, 1995. |

19 | G. Crippen and T. Havel. Distance Geometry and Molecular Conformation. John Wiley and Sons, 1988. |

20 | I. Emiris and I. Psarros. "Counting Euclidean Embeddings of line rigid graphs". 2014. |

21 | A. Mukhopadhyay, P. Sarker and K. Kannan. "Randomized versus deterministic point placement algorithms: An experimental study". In ICCSA, Banff, 2015. |

22 | M. Alam and A. A. Mukhopadhyay. "A new algorithm and improved lower bound for point placement on a line in two rounds". In Proceedings of the 22nd Canadian Conference on Computational Geometry, 2010. |

23 | M. Alam and A. Mukhopadhyay. "Improved upper and lower bounds for the point placement problem". 2012. |

Dr. Asish Mukhopadhyay

School of Computer Science,
University of Windsor - Canada

asishm@uwindsor.ca

Mr. Pijus K. Sarker

ValidateIt Technologies Inc. - Canada

Mr. Kishore Kumar V. Kannnan

IBM Canada Ltd. - Canada