Home > CSC-OpenAccess Library > Manuscript Information
EXPLORE PUBLICATIONS BY COUNTRIES |
 |
 |
EUROPE |
|
MIDDLE EAST |
|
ASIA |
|
AFRICA |
| ............................. | |
|
United States of America |
|
United Kingdom |
|
Canada |
|
Australia |
|
Italy |
|
France |
|
Brazil |
|
Germany |
|
Malaysia |
|
Turkey |
|
China |
|
Taiwan |
|
Japan |
|
Saudi Arabia |
|
Jordan |
|
Egypt |
|
United Arab Emirates |
|
India |
|
Nigeria |
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 |
| 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
|
|
|
|
| View all special issues >> | |
|
|
