Article

Quadratic and cubic b-splines by generalizing higher-order voronoi diagrams

Authors:

Yuanxin Liu,

Jack SnoeyinkAuthors Info & Claims

SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

Pages 150 - 157

https://doi.org/10.1145/1247069.1247100

Published: 06 June 2007 Publication History

Get Access

Abstract

A long-standing problem in spline theory has been to generalize classic B-splines to the multivariate setting, and its full solution will have broad impact. We initiate a study of triangulations that generalize the duals of higher order Voronoi diagrams, and show that these can serve as a foundation for a family of multivariate splines that generalize the classic univariate B-splines. This paper focuseson Voronoi diagrams of orders two and three, which produce families of quadratic and cubic bivariate B-splines. We believe that these families are the most general bivariate B-splines to date and supportour belief by demonstrating that a classic quadratic box spline, the Zwart-Powell (ZP) element, is contained in our family. Our work is directly based on that of Neamtu, who established the fascinating connection between splines and higher order Voronoi diagrams.

References

[1]

A. Andrzejak and E. Welzl. In between k-sets, j-factes, and i-faces: (i,j)-partitions. Discrete and Computational geometry, 29(1):105--131, 2003.

Crossref

Google Scholar

[2]

F. Aurenhammer and O. Schwarzkopf. A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. Internat. J. Comput. Geom. Appl., 2:363--381, 1992.

Crossref

Google Scholar

[3]

J.-D. Boissonnat, O. Devillers, and M. Teillaud. A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis. Algorithmica, 9:329--356, 1993.

Crossref

Google Scholar

[4]

C. de Boor. Splines as linear combinations of B-splines. a survey. Approximation Theory, II, pages 1--47, 1976.

Google Scholar

[5]

C. de Boor and K. Höllig. B-splines from parallelepipeds. J. Analyse Math., 42:99--115, 1982.

Crossref

Google Scholar

[6]

C. de Boor, K. Höllig, and S.D. Riemenschneider. Box Splines. Springer-Verlag, New York, 1993.

Digital Library

Google Scholar

[7]

D.T. Lee. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput., C-31:478--487, 1982.

Digital Library

Google Scholar

[8]

M. Neamtu. What is the natural generalization of univariate splines to higher dimensions? Mathematical Methods for Curves and Surfaces: Oslo 2000, pages 355--392, 2001.

Digital Library

Google Scholar

[9]

M. Neamtu. Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay. Trans. Amer. Math. Soc., 2004. to appear, http://math.vanderbilt.edu/~neamtu/papers/papers.html.

Google Scholar

[10]

B. Dembart, D. Gonsor, and M. Neamtu. Bivariate quadratic B-splines used as basis functions for data fitting. 2004. to appear, http://math.vanderbilt.edu/~neamtu/papers/papers.html.

Google Scholar

[11]

L. Ramshaw. Blossoms are polar forms. Comput. Aided Geom. Design, 6(4):323--358, 1989.

Digital Library

Google Scholar

[12]

D. Schmitt and J.-C. Spehner. k-set polytopes and order-k Delaunay diagrams. In International Symposium on Voronoi Diagrams in Science and Engineering, pages 173--185, 2006.

Digital Library

Google Scholar

Cited By

View all

Wang ZCao JWei XChen ZCasquero HZhang Y(2023)Kirchhoff–Love shell representation and analysis using triangle configuration B-splinesComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2023.116316416(116316)Online publication date: Nov-2023
https://doi.org/10.1016/j.cma.2023.116316
Grošelj JSpeleers H(2023)Extraction and application of super-smooth cubic B-splines over triangulationsComputer Aided Geometric Design10.1016/j.cagd.2023.102194(102194)Online publication date: Apr-2023
https://doi.org/10.1016/j.cagd.2023.102194
Zhu HCao JXiao YChen ZZhong ZZhang Y(2022)TCB-spline-based Image VectorizationACM Transactions on Graphics10.1145/351313241:3(1-17)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3513132
Show More Cited By

Index Terms

Quadratic and cubic b-splines by generalizing higher-order voronoi diagrams
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Voronoi splines

-We introduce a framework for construction of non-separable multivariate splines that are geometrically tailored for general sampling lattices. Voronoi splines are B-spline-like elements that inherit the geometry of a sampling lattice from its Voronoi ...
Data Reduction Using Cubic Rational B-Splines

A geometric method for fitting rational cubic B-spline curves to data representing smooth curves, such as intersection curves or silhouette lines, is presented. The algorithm relies on the convex hull and on the variation diminishing properties of ...
Refining cubic parametric B-splines
Special issue on Geometric Modeling (Dagstuhl 2005)

We present refinement properties of cubic parametric B-splines: a family of functions introduced some years ago in the context of shape-preserving approximation of curves. The refinement equations determine a related subdivision scheme which turns out ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

June 2007

404 pages

ISBN:9781595937056

DOI:10.1145/1247069

Program Chair:
Jeff Erickson
University of Illinois, Urbana-Champaign, USA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
387
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang ZCao JWei XChen ZCasquero HZhang Y(2023)Kirchhoff–Love shell representation and analysis using triangle configuration B-splinesComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2023.116316416(116316)Online publication date: Nov-2023
https://doi.org/10.1016/j.cma.2023.116316
Grošelj JSpeleers H(2023)Extraction and application of super-smooth cubic B-splines over triangulationsComputer Aided Geometric Design10.1016/j.cagd.2023.102194(102194)Online publication date: Apr-2023
https://doi.org/10.1016/j.cagd.2023.102194
Zhu HCao JXiao YChen ZZhong ZZhang Y(2022)TCB-spline-based Image VectorizationACM Transactions on Graphics10.1145/351313241:3(1-17)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3513132
Wang ZCao JWei XZhang Y(2022)TCB-spline-based isogeometric analysis method with high-quality parameterizationsComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2022.114771393(114771)Online publication date: Apr-2022
https://doi.org/10.1016/j.cma.2022.114771
Schmitt D(2021)Bivariate B-splines from convex configurationsJournal of Computer and System Sciences10.1016/j.jcss.2021.03.002Online publication date: Mar-2021
https://doi.org/10.1016/j.jcss.2021.03.002
Chevallier NFruchard ASchmitt DSpehner J(2020)Separation by Convex Pseudo-CirclesDiscrete & Computational Geometry10.1007/s00454-020-00190-3Online publication date: 31-Mar-2020
https://doi.org/10.1007/s00454-020-00190-3
Cao JChen ZWei XZhang Y(2019)A finite element framework based on bivariate simplex splines on triangle configurationsComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2019.112598357(112598)Online publication date: Dec-2019
https://doi.org/10.1016/j.cma.2019.112598
Schmitt D(2019)Bivariate B-Splines from Convex Pseudo-circle ConfigurationsFundamentals of Computation Theory10.1007/978-3-030-25027-0_23(335-349)Online publication date: 10-Jul-2019
https://doi.org/10.1007/978-3-030-25027-0_23
Chevallier NFruchard ASchmitt DSpehner JCheng SDevillers O(2014)Separation by Convex Pseudo-CirclesProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582148(444-453)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582148

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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Voronoi splines

Data Reduction Using Cubic Rational B-Splines

Refining cubic parametric B-splines

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations