research-article

A polynomial time algorithm for multivariate interpolation in arbitrary dimension via the Delaunay triangulation

Authors:

Tyler H. Chang,

Layne T. Watson,

Thomas C. H. Lux,

Kirk W. Cameron,

Yili HongAuthors Info & Claims

ACMSE '18: Proceedings of the 2018 ACM Southeast Conference

Article No.: 12, Pages 1 - 8

https://doi.org/10.1145/3190645.3190680

Published: 29 March 2018 Publication History

Abstract

The Delaunay triangulation is a fundamental construct from computational geometry, which finds wide use as a model for multivariate piecewise linear interpolation in fields such as geographic information systems, civil engineering, physics, and computer graphics. Though efficient solutions exist for computation of two- and three-dimensional Delaunay triangulations, the computational complexity for constructing the complete Delaunay triangulation grows exponentially in higher dimensions. Therefore, usage of the Delaunay triangulation as a model for interpolation in high-dimensional domains remains computationally infeasible by standard methods. In this paper, a polynomial time algorithm is presented for interpolating at a finite set of points in arbitrary dimension via the Delaunay triangulation. This is achieved by computing a small subset of the simplices in the complete triangulation, such that all interpolation points lie in the support of the subset. An empirical study on the runtime of the proposed algorithm is presented, demonstrating its scalability to high-dimensional spaces.

References

[1]

C Bradford Barber, David P Dobkin, and Hannu Huhdanpaa. 1996. The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software (TOMS) 22, 4 (1996), 469--483.

Digital Library

[2]

Jean-Daniel Boissonnat, Olivier Devillers, and Samuel Hornus. 2009. Incremental Construction of the Delaunay Triangulation and the Delaunay Graph in Medium Dimension. In Proceedings of the twenty-fifth annual symposium on Computational geometry. ACM, 208--216.

Digital Library

[3]

Jean-Daniel Boissonnat and Monique Teillaud. 1993. On the randomized construction of the Delaunay tree. Theoretical Computer Science 112, 2 (1993), 339--354.

Digital Library

[4]

Adrian Bowyer. 1981. Computing Dirichlet tessellations. Comput. J. 24, 2 (1981), 162--166.

[5]

Siu-Wing Cheng, Tamal K Dey, and Jonathan Shewchuk. 2012. Delaunay Mesh Generation. CRC Press.

Digital Library

[6]

Paolo Cignoni, Claudio Montani, and Roberto Scopigno. 1998. DeWall: A Fast Divide & Conquer Delaunay Triangulation Algorithm in Ed. Computer-Aided Design 30, 5 (1998), 333--341.

[7]

Mark de Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars. 2008. Computational Geometry: Algorithms and Applications (third ed.). Springer-Verlag Berlin Heidelberg.

Digital Library

[8]

Herbert Edelsbrunner. 1989. An acyclicity theorem for cell complexes in d dimensions. In Proceedings of the fifth annual symposium on Computational geometry. ACM, 145--151.

Digital Library

[9]

Herbert Edelsbrunner and Ernst Peter Mücke. 1990. Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms. ACM Transactions on Graphics (TOG) 9, 1 (1990), 66--104.

Digital Library

[10]

Richard J Hanson and Karen H Haskell. 1982. Algorithm 587: Two Algorithms for the Linearly Constrained Least Squares Problem. ACM Transactions on Mathematical Software (TOMS) 8, 3 (1982), 323--333.

Digital Library

[11]

Victor Klee. 1980. On the complexityof d-dimensionalVoronoi diagrams. Archiv der Mathematik 34, 1 (1980), 75--80.

[12]

Ernst P Mücke, Isaac Saias, and Binhai Zhu. 1999. Fast randomized point location without preprocessing in two-and three-dimensional Delaunay triangulations. Computational Geometry 12, 1--2 (1999), 63--83.

Digital Library

[13]

Stephen M Omohundro. 1990. Geometric Learning Algorithms. Physica D: Nonlinear Phenomena 42, 1--3 (1990), 307--321.

Digital Library

[14]

VT Rajan. 1994. Optimality of the Delaunay Triangulation in Rd. Discrete & Computational Geometry 12, 2 (1994), 189--202.

Digital Library

[15]

WE Schaap and R Van De Weygaert. 2000. Continuous Fields and Discrete Samples: Reconstruction through Delaunay Tessellations. Astronomy and Astrophysics 363 (2000), L29--L32.

[16]

Peter Su and Robert L Scot Drysdale. 1995. A Comparison of Sequential Delaunay Triangulation Algorithms. In Proceedings of the eleventh annual symposium on Computational geometry. ACM, 61--70.

Digital Library

[17]

David F Watson. 1981. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput. J. 24, 2 (1981), 167--172.

Cited By

Gillette AKur E(2024)Algorithm 1049: The Delaunay Density DiagnosticACM Transactions on Mathematical Software10.1145/370013450:4(1-21)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1145/3700134
Chang TWatson LLeyffer SLux TAlmohri H(2024)Remark on Algorithm 1012: Computing Projections with Large DatasetsACM Transactions on Mathematical Software10.1145/365658150:2(1-8)Online publication date: 28-Jun-2024
https://dl.acm.org/doi/10.1145/3656581
Sultangazin APannocchi LFraile LTabuada P(2024)Learning to Control Known Feedback Linearizable Systems From DemonstrationsIEEE Transactions on Automatic Control10.1109/TAC.2023.327239269:1(189-201)Online publication date: Jan-2024
https://doi.org/10.1109/TAC.2023.3272392
Show More Cited By

Recommendations

Predicting system performance by interpolation using a high-dimensional delaunay triangulation
HPC '18: Proceedings of the High Performance Computing Symposium

When interpolating computing system performance data, there are many input parameters that must be considered. Therefore, the chosen multivariate interpolation model must be capable of scaling to many dimensions. The Delaunay triangulation is a ...
A spectral characterization of the Delaunay triangulation

The Delaunay triangulation of a planar point set is a fundamental construct in computational geometry. A simple algorithm to generate it is based on flips of diagonal edges in convex quads. We characterize the effect of a single edge flip in a ...
Fast centroidal Voronoi Delaunay triangulation for unstructured mesh generation

A fast unstructured mesh generation algorithm based on conforming centroidal Voronoi Delaunay triangulation (CfCVDT) algorithm (Ju, 2007) is proposed in this paper. In the new algorithm, the constrained Delaunay triangulation (CDT) algorithm is used ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACMSE '18: Proceedings of the 2018 ACM Southeast Conference

March 2018

246 pages

ISBN:9781450356961

DOI:10.1145/3190645

Conference Chair:
Ka-Wing Wong
Eastern Kentucky University
,
Program Chair:
Chi Shen
Kentucky State University
,
Publications Chair:
Dana Brown
Bluegrass Community & Technical College

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 March 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ACM SE '18

Sponsor:

ACM

ACM SE '18: Southeast Conference

March 29 - 31, 2018

Kentucky, Richmond

Acceptance Rates

ACMSE '18 Paper Acceptance Rate 34 of 41 submissions, 83%;

Overall Acceptance Rate 502 of 1,023 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
193
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gillette AKur E(2024)Algorithm 1049: The Delaunay Density DiagnosticACM Transactions on Mathematical Software10.1145/370013450:4(1-21)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1145/3700134
Chang TWatson LLeyffer SLux TAlmohri H(2024)Remark on Algorithm 1012: Computing Projections with Large DatasetsACM Transactions on Mathematical Software10.1145/365658150:2(1-8)Online publication date: 28-Jun-2024
https://dl.acm.org/doi/10.1145/3656581
Sultangazin APannocchi LFraile LTabuada P(2024)Learning to Control Known Feedback Linearizable Systems From DemonstrationsIEEE Transactions on Automatic Control10.1109/TAC.2023.327239269:1(189-201)Online publication date: Jan-2024
https://doi.org/10.1109/TAC.2023.3272392
Wang YXu LHong YPan RChang TLux TBernard JWatson LCameron K(2022)Design strategies and approximation methods for high-performance computing variability managementJournal of Quality Technology10.1080/00224065.2022.203528555:1(88-103)Online publication date: 17-Feb-2022
https://doi.org/10.1080/00224065.2022.2035285
Lux TWatson LChang THong YCameron K(2021)Interpolation of sparse high-dimensional dataNumerical Algorithms10.1007/s11075-020-01040-288:1(281-313)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s11075-020-01040-2
Jrad MKapania RSchetz JWatson L(2019)Self-Learning, Adaptive Software for Aerospace Engineering Applications: Example of Oblique Shocks in Supersonic FlowAIAA Scitech 2019 Forum10.2514/6.2019-1704Online publication date: 6-Jan-2019
https://doi.org/10.2514/6.2019-1704
Lux TNagy SAlmanaa MYao SBixler R(2019)A Case Study on a Sustainable Framework for Ethically Aware Predictive Modeling2019 IEEE International Symposium on Technology and Society (ISTAS)10.1109/ISTAS48451.2019.8937885(1-7)Online publication date: Nov-2019
https://doi.org/10.1109/ISTAS48451.2019.8937885

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents