2015/02/28 by Matteo Gallet, Christoph Koutschan, Zijia Li +3 · 39 citations
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Algebra over a field #Algorithm #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Construct (python library) #Factorization #Generality #Geometry #Linkage (software) #Mathematical analysis #Mathematics #Noncommutative geometry #Parametric equation #Parametric statistics #Planar #Plane (geometry) #Plane curve #Polynomial and algebraic computation #Programming language #Pure mathematics #Symbolic computation #Task (project management) #Theoretical computer science #Tracing #cs.CG #cs.RO #cs.SC #math.AG #math.RA #msc:12Y05 #msc:14P05 #msc:16Z05 #msc:20G20 #msc:68W30 #msc:70B15 #msc:70G55
paper · pdf · doi:10.1090/mcom/3120
published in Mathematics of Computation 86(303), 473-506 (American Mathematical Society) · 33 pages, 12 figures
openalex publication_date 2016/03/23 · arxiv created 2016/04/05 · arxiv updated 2016/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Designing mechanical devices, called linkages, that draw a given plane curve has been a topic that interested engineers and mathematicians for hundreds of years, and recently also computer scientists. Already in 1876, Kempe proposed a procedure for solving the problem in full generality, but his constructions tend to be extremely complicated. We provide a novel algorithm that produces much simpler linkages, but works only for parametric curves. Our approach is to transform the problem into a factorization task over some noncommutative algebra. We show how to compute such a factorization, and how to use it to construct a linkage tracing a given curve.