Marin, DianaOhrhallinger, StefanWimmer, MichaelUmetani, NobuyukiWojtan, ChrisVouga, Etienne2022-10-042022-10-0420221467-8659https://doi.org/10.1111/cgf.14654https://diglib.eg.org:443/handle/10.1111/cgf14654Determining connectivity between points and reconstructing their shape boundaries are long-standing problems in computer graphics. One possible approach to solve these problems is to use a proximity graph. We propose a new proximity graph computed by intersecting the to-date rarely used proximity-based graph called spheres-of-influence graph (SIG) with the Delaunay triangulation (DT). We prove that the resulting graph, which we name SIGDT, contains the piece-wise linear reconstruction for a set of unstructured points in the plane for a sampling condition superseding current bounds and capturing well practical point sets' properties. As an application, we apply a dual of boundary adjustment steps from the CONNECT2D algorithm to remove the redundant edges. We show that the resulting algorithm SIG-CONNECT2D yields the best reconstruction accuracy compared to state-of-the-art algorithms from a recent comprehensive benchmark, and the method offers the potential for further improvements, e.g., for surface reconstruction.CCS Concepts: Computing methodologies → Point-based modelsComputing methodologies → Pointbased models10.1111/cgf.1465425-3612 pages