Search

We provide a set of tools for generating planar embeddings of triangulated topological spheres. The algorithms make use of Schnyder labelings and realizers. A new representation of the realizer based on dual trees leads to a simple linear time algorithm mapping from weights per triangle to barycentric coordinates and, more importantly, also in the reverse direction. The algorithms can be implemented so that all coefficients involved are 1 or -1. This enables integer computation, making all computations exact. Being a Schnyder realizer, mapping from positive triangle weights guarantees that the barycentric coordinates form an embedding. The reverse direction enables an algorithm for fixing flipped triangles in planar realizations, by mapping from coordinates to weights and adjusting the weights (without forcing them to be positive). In a range of experiments, we demonstrate that all algorithms are orders of magnitude faster than existing robust approaches. [ABSTRACT FROM AUTHOR]

Let h(x) be a non constant polynomial with rational coefficients. Our aim is to introduce the h(x)-Chebyshev polynomials of the first and second kind Tn and Un. We show that they are in a ℚ-vectorial subspace En(x) of ℚ[x] of dimension n. We establish that the polynomial sequences (hkTn−k)k and (hkUn−k)k, (0 ≤ k ≤ n − 1) are two bases of En(x) for which Tn and Un admit remarkable integer coordinates.

A novel approach for a robust computation of positional relations of two-dimensional geometric features is presented which guarantees reliable results, provided that the initial data is valid. The method is based on the use of integer coordinates and a method to generate a complete, gap-less and non-overlapping spatial decomposition. The spatial relationships of two geometric features are then represented using DE-9IM matrices. These allow the spatial relationships to be represented compactly. The DE-9IM matrices are based on the spatial decomposition using explicit neighborhood relations. No further geometric calculations are required for their computation. Based on comparative tests, it could be proven that this approach, up to a predictable limit, provides correct results and thus offers advantages over classical methods for the calculation of spatial relationships. This novel method can be used in all fields, especially where guaranteed reliable results are required.

We analyze mathematical aspects of one of the fundamental data analysis problems consisting in the search (selection) for the subset with the largest number of similar elements among a collection of objects. In particular, the problem appears in connection with the analysis of data in the form of time series (discrete signals). One of the problems in modeling this challenge is considered, namely, the problem of finding the cluster of the largest size (cardinality) in a 2-partition of a finite sequence of points in Euclidean space into two clusters (subsequences) under two constraints. The first constraint is on the choice of the indices of elements included in the clusters. This constraint simulates the set of time-admissible configurations of similar elements in the observed discrete signal. The second constraint is imposed on the value of the quadratic clustering function. This constraint simulates the level of intracluster proximity of objects. The clustering function under the second constraint is the sum (over both clusters) of the intracluster sums of squared distances between the cluster elements and its center. The center of one of the clusters is unknown and defined as the centroid (the arithmetic mean over all elements of this cluster). The center of the other cluster is the origin. Under the first constraint, the difference between any two subsequent indices of elements contained in a cluster with an unknown center is bounded above and below by some constants. It is established in the paper that the optimization problem under consideration, which models one of the simplest significant problems of data analysis, is strongly NP-hard. We propose an exact algorithm for the case of a problem with integer coordinates of its input points. If the dimension of the space is bounded by a constant, then the algorithm is pseudopolynomial. [ABSTRACT FROM AUTHOR]

Letting Tn (resp. Un) be the n-th Chebyshev polynomials of the first (resp. second) kind, we prove that the sequences (XkTn-k)k and (XkUn-k)k for n - 2 ⌊n/2⌋ ≤ k ≤ n - ⌊n/2⌋ are two basis of the ℚ-vectorial space 픸n [X] formed by the polynomials of ℚ[X] having the same parity as n and of degree ≤ n. Also Tn and Un admit remarkableness integer coordinates on each of the two basis. [ABSTRACT FROM AUTHOR]

Computational geometry classically assumes real-number arithmetic which does not exist in actual computers. A solution consists in using integer coordinates for data and exact arithmetic for computations. This approach implies that if the results of an algorithm are the input of another, these results must be rounded to match this hypothesis of integer coordinates. In this paper, we treat the case of two-dimensional Voronoi diagrams and are interested in rounding the Voronoi vertices to grid points while interesting properties of the Voronoi diagram are preserved. These properties are the planarity of the embedding and the convexity of the cells. We give a condition on the grid size to ensure that rounding to the nearest grid point preserves the properties. We also present heuristics to round vertices (not to the nearest grid point) and preserve these properties. [Copyright &y& Elsevier]

Given a dataset of two‐dimensional points in the plane with integer coordinates, the method proposed reduces a set of n points down to a set of s points s ≤ n, such that the convex hull on the set of s points is the same as the convex hull of the original set of n points. The method is O(n). It helps any convex hull algorithm run faster. The empirical analysis of a practical case shows a percentage reduction in points of over 98%, that is reflected as a faster computation with a speedup factor of at least 4. [ABSTRACT FROM AUTHOR]