DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cheong, Otfried | ko |
dc.contributor.author | Everett, H | ko |
dc.contributor.author | Kim, KS | ko |
dc.contributor.author | Lazard, S | ko |
dc.contributor.author | Schott, R | ko |
dc.date.accessioned | 2008-11-03T01:35:19Z | - |
dc.date.available | 2008-11-03T01:35:19Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 2007-08 | - |
dc.identifier.citation | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, v.17, no.4, pp.349 - 360 | - |
dc.identifier.issn | 0218-1959 | - |
dc.identifier.uri | http://hdl.handle.net/10203/7726 | - |
dc.description.abstract | Given 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.sponsorship | This research was supported by the French-Korean Science and Technology Amicable Relationships program (STAR). | en |
dc.language | English | - |
dc.language.iso | en_US | en |
dc.publisher | WORLD SCIENTIFIC PUBL CO PTE LTD | - |
dc.subject | VORONOI DIAGRAMS | - |
dc.subject | RAY | - |
dc.title | Parabola separation queries and their applicationto stone throwing | - |
dc.type | Article | - |
dc.identifier.wosid | 000251316600004 | - |
dc.identifier.scopusid | 2-s2.0-34548085688 | - |
dc.type.rims | ART | - |
dc.citation.volume | 17 | - |
dc.citation.issue | 4 | - |
dc.citation.beginningpage | 349 | - |
dc.citation.endingpage | 360 | - |
dc.citation.publicationname | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | - |
dc.identifier.doi | 10.1142/S0218195907002379 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | Everett, H | - |
dc.contributor.nonIdAuthor | Kim, KS | - |
dc.contributor.nonIdAuthor | Lazard, S | - |
dc.contributor.nonIdAuthor | Schott, R | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | ray shooting | - |
dc.subject.keywordAuthor | simple polygon | - |
dc.subject.keywordAuthor | parabola separation queries | - |
dc.subject.keywordAuthor | parabolic arc | - |
dc.subject.keywordPlus | VORONOI DIAGRAMS | - |
dc.subject.keywordPlus | RAY | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.