Michelucci, D.Neveu, M.Gershon Elber and Nicholas Patrikalakis and Pere Brunet2016-02-172016-02-1720043-905673-55-X1811-7783https://doi.org/10.2312/sm.20041405Abstract A polynomial method is described for computing the shortest circuit with a prescribed homotopy on a surface. The surface is not described by a mesh but by a constellation: a set of sampling points. Points close enough (their distance is less than a prescribed threshold) are linked with an edge: the induced graph is not a triangulation but still permits to compute homologic and homotopic properties. Advantages of constellations over meshes are their simplicity and robustness.I.3.3 [Computer Graphics]Computational Geometry and Object Modeling10.2312/sm.20041405297-302