Publikation: Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
We 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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
LU, Yucheng, Luyu CHENG, Tobias ISENBERG, Chi-Wing FU, Guoning CHEN, Hui LIU, Oliver DEUSSEN, Yunhai WANG, 2021. Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves. In: Computer Graphics Forum. Wiley-Blackwell. 2021, 40(2), pp. 461-474. ISSN 0167-7055. eISSN 1467-8659. Available under: doi: 10.1111/cgf.142647BibTex
@article{Lu2021Curve-54294, year={2021}, doi={10.1111/cgf.142647}, title={Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves}, number={2}, volume={40}, issn={0167-7055}, journal={Computer Graphics Forum}, pages={461--474}, author={Lu, Yucheng and Cheng, Luyu and Isenberg, Tobias and Fu, Chi-Wing and Chen, Guoning and Liu, Hui and Deussen, Oliver and Wang, Yunhai} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/54294"> <dc:contributor>Liu, Hui</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Fu, Chi-Wing</dc:creator> <dc:contributor>Cheng, Luyu</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Isenberg, Tobias</dc:creator> <dcterms:issued>2021</dcterms:issued> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:title>Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves</dcterms:title> <dc:creator>Deussen, Oliver</dc:creator> <dc:creator>Chen, Guoning</dc:creator> <dc:language>eng</dc:language> <dc:creator>Lu, Yucheng</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-07-13T10:59:34Z</dc:date> <dc:contributor>Wang, Yunhai</dc:contributor> <dcterms:abstract xml:lang="eng">We 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.</dcterms:abstract> <dc:contributor>Chen, Guoning</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-07-13T10:59:34Z</dcterms:available> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/54294/1/Lu_2-1ptt4v7c4h9us6.pdf"/> <dc:creator>Cheng, Luyu</dc:creator> <dc:contributor>Isenberg, Tobias</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/54294"/> <dc:contributor>Deussen, Oliver</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Wang, Yunhai</dc:creator> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/54294/1/Lu_2-1ptt4v7c4h9us6.pdf"/> <dc:contributor>Fu, Chi-Wing</dc:contributor> <dc:rights>terms-of-use</dc:rights> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:creator>Liu, Hui</dc:creator> <dc:contributor>Lu, Yucheng</dc:contributor> </rdf:Description> </rdf:RDF>