Premium
Greedy Cut Construction for Parameterizations
Author(s) -
Zhu Tianyu,
Ye Chunyang,
Chai Shuangming,
Fu XiaoMing
Publication year - 2020
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.13923
Subject(s) - distortion (music) , feature (linguistics) , process (computing) , set (abstract data type) , greedy algorithm , point (geometry) , algorithm , construct (python library) , tree (set theory) , mathematics , computer science , reduction (mathematics) , artificial intelligence , pattern recognition (psychology) , mathematical optimization , geometry , combinatorics , computer network , amplifier , linguistics , philosophy , bandwidth (computing) , programming language , operating system
We present a novel method to construct short cuts for parameterizations with low isometric distortion. The algorithm contains two steps: (i) detect feature points, where the distortion is usually concentrated; and (ii) construct a cut by connecting the detected feature points. Central to each step is a greedy method. After generating a redundant feature point set, a greedy filtering process is performed to identify the feature points required for low isometric distortion parameterizations. This filtering process discards the feature points that are useless for distortion reduction while still enabling us to obtain low isometric distortion. Next, we formulate the process of connecting the detected feature points as a Steiner tree problem. To find an approximate solution, we first successively and greedily produce a collection of auxiliary points. Then, a cut is constructed by connecting the feature points and auxiliary points. In the 26,299 test cases in which an exact solution to the Steiner tree problem is available, the length of the cut obtained by our method is on average 0.17% longer than optimal. Compared to state‐of‐the‐art cut construction methods, our method is one order of magnitude faster and generates shorter cuts while achieving similar isometric distortion.