The complexity of flow on fat terrains and its I/O-efficient computation

Cited 6 time in webofscience Cited 0 time in scopus
  • Hit : 1559
  • Download : 585
DC FieldValueLanguage
dc.contributor.authorde Berg, Markko
dc.contributor.authorCheong, Otfriedko
dc.contributor.authorHaverkort, Hermanko
dc.contributor.authorLim, Jung-Gunko
dc.contributor.authorToma, Laurako
dc.date.accessioned2010-02-25T01:45:47Z-
dc.date.available2010-02-25T01:45:47Z-
dc.date.created2012-02-06-
dc.date.created2012-02-06-
dc.date.issued2010-05-
dc.identifier.citationCOMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.43, no.4, pp.331 - 356-
dc.identifier.issn0925-7721-
dc.identifier.urihttp://hdl.handle.net/10203/16799-
dc.description.abstractWe study the complexity and the I/O-efficient computation of flow oil triangulated terrains. We present an acyclic graph, the descent graph, that enables Lis to trace flow paths in triangulations I/O-efficiently. We use the descent graph to obtain I/O-efficient algorithms for Computing river networks and watershed-area maps in O(Sort(d + r)) I/O's where, r is the complexity of the river network and d of the descent graph. Furthermore we describe a data structure based on the subdivision of the terrain induced by the edges of the triangulation and paths of steepest ascent and descent from its vertices. This data structure can be used to report the boundary of the watershed of a query point q or the flow path from q in O(l(s) + Scan(k)) I/O's, where s is the complexity of the subdivision underlying the data structure, l(s) is the number of I/O's used for planar point location in this Subdivision, and k is the size of the reported output. On alpha-fat terrains, that is, triangulated terrains where the minimum angle of any triangle is bounded from below by alpha, we show that the worst-case complexity of the descent graph and of any path of steepest descent is O(n/alpha(2)), where n is the number of triangles in the terrain. The worst-case complexity of the river network and the above-mentioned data structure oil such terrains is O(n(2)/alpha(2)). When or is a positive constant this improves the corresponding bounds for arbitrary terrains by a linear factor. We prove that similar bounds cannot be proven for Delaunay triangulations: these can have river networks of complexity Theta(n(3)). (C) 2009 Elsevier B.V. All rights reserved.-
dc.languageEnglish-
dc.language.isoen_USen
dc.publisherELSEVIER SCIENCE BV-
dc.subjectMODELS-
dc.titleThe complexity of flow on fat terrains and its I/O-efficient computation-
dc.typeArticle-
dc.identifier.wosid000274994100002-
dc.identifier.scopusid2-s2.0-73549102161-
dc.type.rimsART-
dc.citation.volume43-
dc.citation.issue4-
dc.citation.beginningpage331-
dc.citation.endingpage356-
dc.citation.publicationnameCOMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS-
dc.identifier.doi10.1016/j.comgeo.2008.12.008-
dc.embargo.liftdate9999-12-31-
dc.embargo.terms9999-12-31-
dc.contributor.localauthorCheong, Otfried-
dc.contributor.nonIdAuthorde Berg, Mark-
dc.contributor.nonIdAuthorHaverkort, Herman-
dc.contributor.nonIdAuthorToma, Laura-
dc.type.journalArticleArticle; Proceedings Paper-
dc.subject.keywordAuthorRiver network-
dc.subject.keywordAuthorWatershed-
dc.subject.keywordAuthorPolyhedral terrain-
dc.subject.keywordAuthorFatness-
dc.subject.keywordAuthorRealistic input models-
dc.subject.keywordPlusMODELS-
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 6 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0