Conference Paper: The point placement problem on a line improved bounds for pairwise distance queries
File Download
(May Require Subscription)
- No File Attached
(May Require Subscription)
- Publisher Website: 10.1007/978-3-540-74126-8_35
- Scopus: eid_2-s2.0-37249023662
- Find via
Supplementary
-
Citations:
-
Appears in Collections:
| Title | The point placement problem on a line improved bounds for pairwise distance queries |
|---|---|
| Authors | Chin, FYL1 Leung, HCM1 Sung, WK2 Yiu, SM1 |
| Issue Date | 2007 |
| Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| Citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4645 LNBI, p. 372-382 [How to Cite?] DOI: http://dx.doi.org/10.1007/978-3-540-74126-8_35 |
| Abstract | In this paper, we study the adaptive version of the point placement problem on a line, which is motivated by a DNA mapping problem. To identify the relative positions of n distinct points on a straight line, we are allowed to ask queries of pairwise distances of the points in rounds. The problem is to find the number of queries required to determine a unique solution for the positions of the points up to translation and reflection. We improved the bounds for several cases. We show that An/3 + O(√n) queries are sufficient for the case of two rounds while the best known result was 3n/2 queries. For unlimited number of rounds, the best result was 4n/3 queries. We obtain a much better result of using 5n/4 + O(√n) queries with three rounds only. We also improved the lower bound of 30n/29 to 17n/16 for the case of two rounds. © Springer-Verlag Berlin Heidelberg 2007. |
| Description | 7th International Workshop on Algorithms in Bioinformatics (WABI 2007), Philadelphia, PA, USA, 8-9 September 2007. This research is supported by the RGC grant HKU7119/05E. |
| ISSN | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| DOI | http://dx.doi.org/10.1007/978-3-540-74126-8_35 |
| References | References in Scopus |
| dc.contributor.author | Chin, FYL |
|---|---|
| dc.contributor.author | Leung, HCM |
| dc.contributor.author | Sung, WK |
| dc.contributor.author | Yiu, SM |
| dc.date.accessioned | 2010-09-25T15:01:31Z |
| dc.date.available | 2010-09-25T15:01:31Z |
| dc.date.issued | 2007 |
| dc.description.abstract | In this paper, we study the adaptive version of the point placement problem on a line, which is motivated by a DNA mapping problem. To identify the relative positions of n distinct points on a straight line, we are allowed to ask queries of pairwise distances of the points in rounds. The problem is to find the number of queries required to determine a unique solution for the positions of the points up to translation and reflection. We improved the bounds for several cases. We show that An/3 + O(√n) queries are sufficient for the case of two rounds while the best known result was 3n/2 queries. For unlimited number of rounds, the best result was 4n/3 queries. We obtain a much better result of using 5n/4 + O(√n) queries with three rounds only. We also improved the lower bound of 30n/29 to 17n/16 for the case of two rounds. © Springer-Verlag Berlin Heidelberg 2007. |
| dc.description.nature | Link_to_subscribed_fulltext |
| dc.description | 7th International Workshop on Algorithms in Bioinformatics (WABI 2007), Philadelphia, PA, USA, 8-9 September 2007. This research is supported by the RGC grant HKU7119/05E. |
| dc.identifier.citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4645 LNBI, p. 372-382 [How to Cite?] DOI: http://dx.doi.org/10.1007/978-3-540-74126-8_35 |
| dc.identifier.doi | http://dx.doi.org/10.1007/978-3-540-74126-8_35 |
| dc.identifier.epage | 382 |
| dc.identifier.hkuros | 161354 |
| dc.identifier.issn | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| dc.identifier.openurl | |
| dc.identifier.scopus | eid_2-s2.0-37249023662 |
| dc.identifier.spage | 372 |
| dc.identifier.uri | http://hdl.handle.net/10722/93450 |
| dc.identifier.volume | 4645 LNBI |
| dc.language | eng |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| dc.publisher.place | Germany |
| dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| dc.relation.references | References in Scopus |
| dc.rights | The original publication is available at www.springerlink.com |
| dc.title | The point placement problem on a line improved bounds for pairwise distance queries |
| dc.type | Conference_Paper |
Author Affiliations
- The University of Hong Kong
- National University of Singapore