BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:Asia/Hong_Kong
X-LIC-LOCATION:Asia/Hong_Kong
BEGIN:STANDARD
TZOFFSETFROM:+0800
TZOFFSETTO:+0800
TZNAME:HKT
DTSTART:19911015T033000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20251218T030656Z
LOCATION:Meeting Room S421\, Level 4
DTSTART;TZID=Asia/Hong_Kong:20251217T131000
DTEND;TZID=Asia/Hong_Kong:20251217T132000
UID:siggraphasia_SIGGRAPH Asia 2025_sess137_papers_1119@linklings.com
SUMMARY:BSP-OT: Sparse transport plans between discrete measures in loglin
 ear time
DESCRIPTION:Baptiste Genest (Université Claude Bernard Lyon, CNRS); Nicola
 s Bonneel (CNRS); Vincent Nivoliers (Université Claude Bernard Lyon); and 
 David Coeurjolly (CNRS, LIRIS)\n\nTo solve the optimal transport problem b
 etween two uniform discrete measures of the same size, one seeks a bijecti
 ve assignment that minimizes some\nmatching cost. For this task, exact alg
 orithms are intractable for large problems, while approximate ones may los
 e the bijectivity of the assignment.\nWe address this issue and the more g
 eneral cases of non-uniform discrete\nmeasures with different total masses
 , where partial transport may be desirable. The core of our algorithm is a
  variant of the Quicksort algorithm\nthat provides an efficient strategy t
 o randomly explore many relevant and\neasy-to-compute couplings, by matchi
 ng BSP trees in loglinear time. The\ncouplings we obtain are as sparse as 
 possible, in the sense that they provide\nbijections, injective partial ma
 tchings or sparse couplings depending on the\nnature of the matched measur
 es. To improve the transport cost, we propose\nefficient strategies to mer
 ge 𝑘 sparse couplings into a higher quality one.\nFor 𝑘= 64, we obtain tra
 nsport plans with typically less than 1% of relative\nerror in a matter of
  seconds between hundreds of thousands of points in 3D\non the CPU. We dem
 onstrate how these high-quality approximations can\ndrastically speed-up u
 sual pipelines involving optimal transport, such as\nshape interpolation, 
 intrinsic manifold sampling, color transfer, topological\ndata analysis, r
 igid partial registration of point clouds and image stippling.\n\nRegistra
 tion Category: Full Access, Full Access Supporter\n\nSession Chair: Oded S
 tein (University of Southern California)\n\n
END:VEVENT
END:VCALENDAR