Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(360.48KB)
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
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.
CITED BY (0)  
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