Computing homotopic line simplification

DOI10.1016/J.COMGEO.2014.02.002MaRDI QIDQ2249045zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 27 June 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2014.02.002

zbMATH Keywords

computational geometryhomotopypath simplification

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

The following problem is investigated: Let \(\mathcal{P}=p_1,p_2,\dots,p_n\) a given polygonal path and \(\mathcal{S}=\{s_1,s_2,\dots,s_m\}\) a set of \(m\) point obstacles in the plane not intersecting \(\mathcal{P}\), and \(\epsilon\) an error defined under a distance function \(F\). The problem is to simplify the path \(\mathcal{P}\) by \(\mathcal{Q}=q_1,q_2,\dots,q_k\) \((q_1=p_1,)\) and \(q_k=p_n\) within the given error \(\epsilon\) so that \(\mathcal{Q}\) is homotopic to \(\mathcal{P}\). The first polynomial-time algorithm computes an optimal homotopic simplification of \(\mathcal{P}\) in \(O(n^6m^2)+T_F(n)\) time, where \(T_F(n)\) is the time to compute all shortcuts \(p_ip_j\) with error of at most \(\epsilon\) under the error measure \(F\). A method is presented that identifies all such shortcuts in \(O(n(m+n)\log(n+m))\) time.

Recommendations

• Computing homology
• Homology Computation
• Computational complexity of a piecewise linear homotopy algorithm
• scientific article; zbMATH DE number 5159382
• Computing curve intersection by homotopy methods
• Computing Homology: A Global Reduction Approach
• Simplification of complexes for persistent homology computations
• HOMOTOPY-PRESERVING MEDIAL AXIS SIMPLIFICATION
• scientific article; zbMATH DE number 2079391

Cites work

• AN OPTIMAL MORPHING BETWEEN POLYLINES
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• Approximating the Fréchet distance for realistic curves in near linear time
• Computational geometry. Algorithms and applications.
• Computing homotopic shortest paths in the plane
• Computing the visibility graph of points within a polygon
• Efficient piecewise-linear function approximation using the uniform metric
• scientific article; zbMATH DE number 4026646 (Why is no real title available?)
• scientific article; zbMATH DE number 4074316 (Why is no real title available?)
• scientific article; zbMATH DE number 4082817 (Why is no real title available?)
• Making data structures persistent
• Near-linear time approximation algorithms for curve simplification
• New similarity measures between polylines with applications to morphing and polygon sweeping
• Optimal simplification of polygonal chains for subpixel-accurate rendering
• Simplifying a polygonal subdivision while keeping it simple
• Streaming algorithms for line simplification
• Testing homotopy for paths in the plane
• The complexity of optimization problems

Cited in

(5)

• Polygonal path simplification with angle constraints
• scientific article; zbMATH DE number 2185597 (Why is no real title available?)
• Computing Homology: A Global Reduction Approach
• Simplexwise Linear Untangling
• Computing optimal homotopies over a spiked plane with polygonal boundary

This page was built for publication: Computing homotopic line simplification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249045)