File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: The point placement problem on a line improved bounds for pairwise distance queries
  • Basic View
  • Metadata View
  • XML View
TitleThe point placement problem on a line improved bounds for pairwise distance queries
 
AuthorsChin, FYL1
Leung, HCM1
Sung, WK2
Yiu, SM1
 
Issue Date2007
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationLecture 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
 
AbstractIn 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.
 
Description7th 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.
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
DOIhttp://dx.doi.org/10.1007/978-3-540-74126-8_35
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorChin, FYL
 
dc.contributor.authorLeung, HCM
 
dc.contributor.authorSung, WK
 
dc.contributor.authorYiu, SM
 
dc.date.accessioned2010-09-25T15:01:31Z
 
dc.date.available2010-09-25T15:01:31Z
 
dc.date.issued2007
 
dc.description.abstractIn 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.natureLink_to_subscribed_fulltext
 
dc.description7th 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.citationLecture 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.doihttp://dx.doi.org/10.1007/978-3-540-74126-8_35
 
dc.identifier.epage382
 
dc.identifier.hkuros161354
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-37249023662
 
dc.identifier.spage372
 
dc.identifier.urihttp://hdl.handle.net/10722/93450
 
dc.identifier.volume4645 LNBI
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 
dc.relation.referencesReferences in Scopus
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.titleThe point placement problem on a line improved bounds for pairwise distance queries
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chin, FYL</contributor.author>
<contributor.author>Leung, HCM</contributor.author>
<contributor.author>Sung, WK</contributor.author>
<contributor.author>Yiu, SM</contributor.author>
<date.accessioned>2010-09-25T15:01:31Z</date.accessioned>
<date.available>2010-09-25T15:01:31Z</date.available>
<date.issued>2007</date.issued>
<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</identifier.citation>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/93450</identifier.uri>
<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.</description>
<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(&#8730;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(&#8730;n) queries with three rounds only. We also improved the lower bound of 30n/29 to 17n/16 for the case of two rounds. &#169; Springer-Verlag Berlin Heidelberg 2007.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<title>The point placement problem on a line improved bounds for pairwise distance queries</title>
<type>Conference_Paper</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0302-9743&amp;volume=4645&amp;spage=372&amp;epage=382&amp;date=2007&amp;atitle=The+point+placement+problem+on+a+line:+improved+bounds+for+pairwise+distance+queries</identifier.openurl>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1007/978-3-540-74126-8_35</identifier.doi>
<identifier.scopus>eid_2-s2.0-37249023662</identifier.scopus>
<identifier.hkuros>161354</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-37249023662&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>4645 LNBI</identifier.volume>
<identifier.spage>372</identifier.spage>
<identifier.epage>382</identifier.epage>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. National University of Singapore