Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves

dc.contributor.authorLu, Yuchengen_US
dc.contributor.authorCheng, Luyuen_US
dc.contributor.authorIsenberg, Tobiasen_US
dc.contributor.authorFu, Chi-Wingen_US
dc.contributor.authorChen, Guoningen_US
dc.contributor.authorLiu, Huien_US
dc.contributor.authorDeussen, Oliveren_US
dc.contributor.authorWang, Yunhaien_US
dc.contributor.editorMitra, Niloy and Viola, Ivanen_US
dc.date.accessioned2021-04-09T08:01:21Z
dc.date.available2021-04-09T08:01:21Z
dc.date.issued2021
dc.description.abstractWe introduce the curve complexity heuristic (CCH), a KD-tree construction strategy for 3D curves, which enables interactive exploration of neighborhoods in dense and large line datasets. It can be applied to searches of k-nearest curves (KNC) as well as radius-nearest curves (RNC). The CCH KD-tree construction consists of two steps: (i) 3D curve decomposition that takes into account curve complexity and (ii) KD-tree construction, which involves a novel splitting and early termination strategy. The obtained KD-tree allows us to improve the speed of existing neighborhood search approaches by at least an order of magnitude (i. e., 28× for KNC and 12× for RNC with 98% accuracy) by considering local curve complexity. We validate this performance with a quantitative evaluation of the quality of search results and computation time. Also, we demonstrate the usefulness of our approach for supporting various applications such as interactive line queries, line opacity optimization, and line abstraction.en_US
dc.description.number2
dc.description.sectionheadersFlow Visualization
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume40
dc.identifier.doi10.1111/cgf.142647
dc.identifier.issn1467-8659
dc.identifier.pages461-474
dc.identifier.urihttps://doi.org/10.1111/cgf.142647
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf142647
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectHuman centered computing
dc.subjectScientific visualization
dc.subjectTheory of computation
dc.subjectNearest neighbor algorithms
dc.titleCurve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curvesen_US
Files
Original bundle
Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
v40i2pp461-474.pdf
Size:
19.34 MB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
paper1023.mp4
Size:
31.39 MB
Format:
Unknown data format
Collections