BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:Asia/Seoul
X-LIC-LOCATION:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:18871231T000000
DTSTART:19881009T020000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20230103T035307Z
LOCATION:Room 325-AB\, Level 3\, West Wing
DTSTART;TZID=Asia/Seoul:20221206T140000
DTEND;TZID=Asia/Seoul:20221206T153000
UID:siggraphasia_SIGGRAPH Asia 2022_sess156_papers_470@linklings.com
SUMMARY:Compressing Geodesic Information for Fast Point-to-Point Geodesic 
 Distance Queries
DESCRIPTION:Technical Communications, Technical Papers, TOG\n\nCompressing
  Geodesic Information for Fast Point-to-Point Geodesic Distance Queries\n\
 nGotsman, Hormann\n\nGeodesic distances between pairs of points on a 3D me
 sh surface are a crucial ingredient of many geometry processing tasks, but
  are notoriously difficult to compute efficiently on demand. We propose a 
 novel method for the compact storage of geodesic distance information, whi
 ch enables answering point-to-point geodesic distance queries very efficie
 ntly. For a triangle mesh with n vertices, if computing the geodesic dista
 nce to all vertices from a single source vertex costs O(f(n)) time, then w
 e generate a database of size O(mn log n) in O((f(n)+m³n) √n) time in a pr
 eprocessing stage, where m is a constant that depends on the geometric com
 plexity of the surface. We achieve this by computing a nested bisection of
  the mesh surface using separator curves and storing compactly-described f
 unctions approximating the distances between each mesh vertex and a small 
 relevant subset of these curves. Using this database, the geodesic distanc
 e between two mesh vertices can then be approximated well by solving a sma
 ll number of simple univariate minimization problems in O(m log n) worst c
 ase time and O(m) average case time. Our method provides an excellent trad
 eoff between the size of the database, query runtime, and accuracy of the 
 result. It can be used to compress exact or approximate geodesic distances
 , e.g., those obtained by VTP (exact), fast DGG, fast marching, or the hea
 t method (approximate) and is very efficient if f(n)=n, as for the fast DG
 G method.\n\nRegistration Category: FULL ACCESS, ON-DEMAND ACCESS\n\nLangu
 age: ENGLISH\n\nFormat: IN-PERSON, ON-DEMAND
URL:https://sa2022.siggraph.org/en/full-program/?id=papers_470&sess=sess15
 6
END:VEVENT
END:VCALENDAR