Parabola separation queries and their applicationto stone throwing

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 1490
  • Download : 437
DC FieldValueLanguage
dc.contributor.authorCheong, Otfriedko
dc.contributor.authorEverett, Hko
dc.contributor.authorKim, KSko
dc.contributor.authorLazard, Sko
dc.contributor.authorSchott, Rko
dc.date.accessioned2008-11-03T01:35:19Z-
dc.date.available2008-11-03T01:35:19Z-
dc.date.created2012-02-06-
dc.date.created2012-02-06-
dc.date.issued2007-08-
dc.identifier.citationINTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, v.17, no.4, pp.349 - 360-
dc.identifier.issn0218-1959-
dc.identifier.urihttp://hdl.handle.net/10203/7726-
dc.description.abstractGiven two sets A and B of m non-crossing line segments in the plane. we show how to compute in O(m log m) time a data structure that uses O(m) storage and supports the following query in O(log m) time: Given a parabola gamma : y = ax(2) + bx + c, does gamma separate A and B? This structure can be used to build a data structure that stores a simple polygon and allows ray-shooting queries along parabolic trajectories with vertical main axis. For a polygon of complexity n, we can answer such "such-throwing" queries in O(log(2) n) time, using O(n log n) storage and O(n log(2) n) preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.-
dc.description.sponsorshipThis research was supported by the French-Korean Science and Technology Amicable Relationships program (STAR).en
dc.languageEnglish-
dc.language.isoen_USen
dc.publisherWORLD SCIENTIFIC PUBL CO PTE LTD-
dc.subjectVORONOI DIAGRAMS-
dc.subjectRAY-
dc.titleParabola separation queries and their applicationto stone throwing-
dc.typeArticle-
dc.identifier.wosid000251316600004-
dc.identifier.scopusid2-s2.0-34548085688-
dc.type.rimsART-
dc.citation.volume17-
dc.citation.issue4-
dc.citation.beginningpage349-
dc.citation.endingpage360-
dc.citation.publicationnameINTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS-
dc.identifier.doi10.1142/S0218195907002379-
dc.contributor.localauthorCheong, Otfried-
dc.contributor.nonIdAuthorEverett, H-
dc.contributor.nonIdAuthorKim, KS-
dc.contributor.nonIdAuthorLazard, S-
dc.contributor.nonIdAuthorSchott, R-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorray shooting-
dc.subject.keywordAuthorsimple polygon-
dc.subject.keywordAuthorparabola separation queries-
dc.subject.keywordAuthorparabolic arc-
dc.subject.keywordPlusVORONOI DIAGRAMS-
dc.subject.keywordPlusRAY-

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0