Guillaume Moroz
Abstract
We consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M, induced by the L2 norm—that is, ‖ f - g‖2 = √∫M(f - g)2. If f is defined by linear interpolation over a triangulation of M with n triangles and g is defined over another such triangulation, the obvious naive algorithm requires Θ(n2) arithmetic operations to compute this distance. We show that it is possible to compute it in O(nlog4 nlog log n) arithmetic operations by reducing the problem to multipoint evaluation of a certain type of polynomials.
We also present several generalizations and an application to terrain matching.
- P. K. Agarwal, B. Aronov, M. van Kreveld, M. Löffler, and R. Silveira. 2010. Computing similarity between piecewise-linear functions. In Proceedings of the 26th Annual Symposium on Computational Geometry. 375--383. Google Scholar
Digital Library
- P. K. Agarwal, B. Aronov, M. van Kreveld, M. Löffler, and R. Silveira. 2013. Computing correlation between piecewise-linear functions. SIAM Journal on Computing 42, 5, 1867--1887.Google ScholarCross Ref
- D. Ajwani, S. Ray, R. Seidel, and H. Tiwary. 2007. On computing the centroid of the vertices of an arrangement and related problems. In Proceedings of the 10th International Conference on Algorithms and Data Structures (WADS’07). 519--528. Google ScholarDigital Library
- B. Chazelle, H. Edelsbrunner, L. J. Guibas, and M. Sharir. 1994. Algorithms for bichromatic line segment problems and polyhedral terrains. Algorithmica 11, 116--132.Google ScholarDigital Library
- G. Elekes, H. Kaplan, and M. Sharir. 2011. On lines, joints, and incidences in three dimensions. Journal of Combinatorial Theory, Series A 118, 962--977. Google ScholarDigital Library
- G. Elekes and M. Sharir. 2010. Incidences in three dimensions and distinct distances in the plane. In Proceedings of the 26th Annual ACM Symposium on Computational Geometry. 413--422. Google ScholarDigital Library
- A. Gajentaan and M. H. Overmars. 1995. On a class of O(n2) problems in computational geometry. Computational Geometry 5, 3, 165--185. Google ScholarDigital Library
- J. von zur Gathen and J. Gerhard. 2003. Modern Computer Algebra (2nd ed.). Cambridge University Press. Google ScholarDigital Library
- L. Guth and N. H. Katz. 2010. Algebraic methods in discrete analogs of the Kakeya problem. Advances in Mathematics 225, 5, 2828--2839.Google ScholarCross Ref
- L. Guth and N. H. Katz. 2011. On the Erdős distinct distances problem in the plane. Annals of Mathematics 181, 1, 155--190.Google Scholar
- H. Kaplan, J. Matoušek, and M. Sharir. 2012. Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique. Discrete & Computational Geometry 48, 3, 499--517. Google ScholarDigital Library
- H. Kaplan, M. Sharir, and E. Shustin. 2010. On lines and joints. Discrete & Computational Geometry 44, 4, 838--843. Google ScholarDigital Library
- K. S. Kedlaya and C. Umans. 2008. Fast modular composition in any characteristic. In Proceedings of the 49th Annual IEEE Symposium on Foundations in Computer Science (FOCS’08). 146--155. Google ScholarDigital Library
- D. Kirkpatrick. 1983. Optimal search in planar subdivisions. SIAM Journal on Computing 12, 1, 28--35.Google ScholarDigital Library
- J. Matoušek. 2011. The dawn of an algebraic era in discrete geometry? In Proceedings of the 27th European Workshop on Computational Geometry (EuroCG’11).Google Scholar
- G. Moroz and B. Aronov. 2012. Computing the distance between piecewise-linear bivariate functions. In Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 288--293. Google ScholarDigital Library
- M. Nüken and M. Ziegler. 2004. Fast multipoint evaluation of bivariate polynomials. In Algorithms—ESA 2004. Lecture Notes in Computer Science, Vol. 3221. Springer, 544--555.Google Scholar
- R. Quilodrán. 2010. The joints problem in Rn. SIAM Journal on Discrete Mathematics 23, 4, 2211--2213. Google ScholarDigital Library
- J. Solymosi and T. Tao. 2012. An incidence theorem in higher dimensions. Discrete & Computational Geometry 48, 2, 255--280. Google ScholarDigital Library
Index Terms
- Computing the Distance between Piecewise-Linear Bivariate Functions
Recommendations
Computing similarity between piecewise-linear functions
SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometryWe study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D - polyhedral terrains - can be transformed vertically by a linear transformation of the ...
Computing Correlation between Piecewise-Linear Functions
We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions---polyhedral terrains---can be transformed vertically by a linear transformation ...
Computing the distance between piecewise-linear bivariate functions
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithmsWe consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M. We focus on the distance induced by the L2-norm, that is [EQUATION]. If f is defined by linear interpolation over ...
Reviews
Vladik Kreinovich
To map a terrain, we measure elevations at different spatial locations and then interpolate the resulting values. Usually, the measurement locations are used to triangulate the area. Then, on each of the resulting triangles, we perform linear interpolation. This is always possible: from the three linear equations corresponding to three known elevations at the three vertices, we can always find three coefficients a 0, a 1, and a 2, which give the interpolated value y = a 0 + a 1 · x 1 + a 2 · x 2. When we have two maps of the same area, it is desirable to gauge how close these maps are, for example, by computing the L 2-difference between the two piecewise-linear functions. If each triangulation uses n triangles, then we can compute the overlay of the two triangulations, and compute the L 2-difference as the sum of integrals over all n 2 triangles from the overlay. However, for large n , this may be too time-consuming. The authors show that the computation of this L 2-difference can be made much faster, in time O ( n · log4( n )), by using a fast multi-point evaluation algorithm for certain polynomials. While for these polynomials, the fast multi-point evaluation algorithm is new, such algorithms are well known for many other polynomials: for example, the fast Fourier transform algorithm is, in effect, a fast multi-point evaluation for an appropriate polynomial. In summary, the authors' novel state-of-the-art algorithm provides a drastic speed-up for the practical important problem of measuring distance between several maps of the same terrain. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments