Home   >   CSC-OpenAccess Library   >    Manuscript Information
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
Volume - 6   Issue - 1    |    Publication Date - June 2016  Table of Contents
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 
A. Daurat, Y. Gérard and M. Nivat. "The chords’ problem". Theor. Comput. Sci., vol. 282, no. 2, p. 319–336, 2002.
A. Mukhopadhyay, P. Sarker and K. Kannan. "Randomized versus deterministic point placement algorithms: An experimental study". In ICCSA, Banff, 2015.
A. Mukhopadhyay, S. Rao, S. Pardeshi and S. Gundlapalli. "Linear Layouts of weakly triangulated graphs". Workshop on Algorithms and Computation, Chennai, 2014.
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.
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.
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.
G. Crippen and T. Havel. Distance Geometry and Molecular Conformation. John Wiley and Sons, 1988.
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.
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.
I. Emiris and I. Psarros. "Counting Euclidean Embeddings of line rigid graphs". 2014.
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.
J. Saxe. "Embeddability of weighted graphs in k-space is strongly NP-hard". 17th Allerton Conference on Communication, Control and Computing, 1979.
L. Blumenthal. Thory and applications of distance geometry, 2nd edition. New York: Chelsea, 1970.
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.
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.
M. Alam and A. Mukhopadhyay. "Improved upper and lower bounds for the point placement problem". 2012.
M. Alam and A. Mukhopadhyay. "Three paths to point placement". In Proceedings of the Conference on Algorithms and Discrete Applied Mathematics, 2015.
M. Bakonyi and C. Johnson. "The euclidean matrix distance completion problem". SIAM J. Matrix Anal. Appl., vol. 16, no. 2, pp. 646-654, 1995.
M. Laurent. "Matrix completion problems". Encyclopedia of Optimization, Second Edition, 2009, pp. 1967-1975.
P. Damaschke. "Point placement on the line by distance data". Discrete Applied Mathematics, vol. 127, no. 1, p. 53–62, 2003.
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.
R. Motawani and P. Raghavan. Randomized Algorithms. New York, NY: Cambridge University Press, 1995.
S. Skiena, W. Smith and P. Lemke. "Reconstructing sets from interpoint distances". In Sixth Annual ACM Symposium on Computational Geometry, New York, 1990.
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