The package DELAUNAYSPARSE (ACM TOMS Algorithm 1012) contains serial and parallel codes, written in FORTRAN 2003 with OpenMP 4.5, for performing interpolation in medium to high dimensions via a sparse subset of the Delaunay triangulation. In addition to the original Fortran source code, this repository contains a wrapper for Python 3.6+ and C bindings. Command line drivers are also provided with the original Fortran code.

DELAUNAYSPARSE contains several modes of operation.

In the original ACM TOMS release, two Fortran driver subroutines were provided:

• DELAUNAYSPARSES runs the serial driver to identify the vertices of the simplex/simplices containing one or more interpolation points. Can also (optionally) be set to compute and return the value of the Delaunay interpolant.
• DELAUNAYSPARSEP runs the parallel driver to identify the vertices of the simplex/simplices containing one or more interpolation points. Can also (optionally) be set to compute and return the value of the Delaunay interpolant (must set the OMP_NUM_THREADS environment variable).

Additionally, two command-line drivers are provided, which read input from files:

• delsparses (uses the serial driver), and
• delsparsep (uses the parallel driver).

In this repository, two additional interfaces are provided for calling from C/C++ (c_binding) and Python 3 (python).

Further detailed user information is documented in the USAGE document.

The physical organization is as follows.

• src contains the original unmodified Fortran source code, as published in ACM TOMS Algorithm 1012. This includes 2 command line drivers samples.f90 (serial driver) and samplep.f90 (parallel driver), which can be used on formatted data files from the command line. Comments at the top of each subroutine document their usage. See this directory's internal README for further information on building, testing, and usage.
• python contains a Python3 wrapper for the Fortran code, allowing DELAUNAYSPARSE to be directly imported as a Python package. This wrapper was created by modifying the output generated by fmodpy. The script example.py demonstrates its usage. For convenience, copies of all Fortran code that is used by the Python wrapper are also included in this directory.
• c_binding contains C bindings for several variations of the main Fortran subroutines, as well as copies of the Fortran source code. A test file test_install.c can be used for usage examples. This directory's internal README also contains best practices when calling Fortran from C/C++.
• docs contains the html source for generating the DelaunaySparse website.
• USAGE provides additional detailed user information.
• DelaunaySparse is shared under the MIT Software License, in the LICENSE file.

To cite this work, please use

@article{TOMSalg1012,
author = {Chang, Tyler H. and Watson, Layne T. and Lux, Thomas C. H. and Butt, Ali R. and Cameron, Kirk W. and Hong, Yili},
title = {Algorithm 1012: {DELAUNAYSPARSE}: {I}nterpolation via a Sparse Subset of the {D}elaunay Triangulation in Medium to High Dimensions},
year = {2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {46},
number = {4},
doi = {10.1145/3422818},
journal = {ACM Trans. Math. Softw.},
month = {nov},
articleno = {38},
numpages = {20}
}

For further inquiries, contact Tyler Chang, [email protected].