On sorting triangles in a delaunay tessellation

In a two-dimensional Delaunay-triangulated domain, there exists a partial ordering of the triangles (with respect to a vertex) that is consistent with the two-dimensional visibility of the triangles from that vertex. An equivalent statement is that a polygon that is star-shaped with respect to a given vertex can be extended, one triangle at a time, until it includes the entire domain. Arbitrary planar triangulations do not possess this useful property which allows incremental processing of the triangles.This work was partially supported by the National Science Foundation's US-Italy Collaborative Research Program under Grant INT-8714578 and Information, Robotics, and Intelligent Research Grant IRI-8704781.     

On balancing sorting on a linear array

A balanced parallel algorithm to sort a sequence of items on a linear array of processors is presented. The length of the sequence may be small to arbitrarily large. For a short sequence, the output of the sorted sequence begins at the step following the last input of the whole sequence. For an arbitrarily long sequence, the time complexity is optimal under realistic hardware conditions. A variation of the algorithm is also introduced. Both algorithms require far less local memory than that required by a different approach of balanced computation. Any number of balanced processors can be connected to deliver more computing power without increasing the memory size of each processor     

On multikey sorting

Few studies of sorting deal with sorting on multikeys. In some applications it is required that the data be sorted on more than one key and in different orders. That is, in ascending on some keys and in descending on some others. In this paper, we propose two different data structures, multikey matrix (MKM) and multikey multilevel linked list (MMLL), and discuss their suitability for multikey sorting. An improved efficiency for multikey sorting is achieved by these data structures. Further, we study their space and time performance and conclude with an algorithm for the distribution of MKM.     

On semantic,pragmatic, and dialectic triangles

A model is built of semantic triangle characterized by its universal nature: it is suitable not only for the elements of the real world but also for any elements of the Universe. Various possibilities of the development of the given model are shown, including a dialectic triangle.     

On sorting and counting

When performing an external sort, an extra integer field added to the sort key can be used to count subsequences, and make the counts available at the beginning of each subsequence.     

On parallel integer sorting

We present an optimal algorithm for sortingn integers in the range [1,n ^c ] (for any constantc) for the EREW PRAM model where the word length isn , for any >0. Using this algorithm, the best known upper bound for integer sorting on the (O(logn) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorthm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.Supported by NSF-DCR-85-03251 and ONR contract N00014-87-K-0310     

Text region extraction in a document image based on the Delaunay tessellation

In this paper, Delaunay triangulation is applied for the extraction of text areas in a document image. By representing the location of connected components in a document image with their centroids, the page structure is described as a set of points in two-dimensional space. When imposing Delaunay triangulation on these points, the text regions in the Delaunay triangulation will have distinguishing triangular features from image and drawing regions. For analysis, the Delaunay triangles are divided into four classes. The study reveals that specific triangles in text areas can be clustered together and identified as text body. Using this method, text regions in a document image containing fragments can also be recognized accurately. Experiments show the method is also very efficient.     

A note on pattern reproduction in tessellation structures

Tessellation structures that reproduce arbitrary patterns are special cases of tessellation structures having local transformations that are linear operators. We introduce a novel formulation of tessellation structures which emphasizes the connection between these structures and concepts of functional analysis. Using this formulation a behavioral analysis technique is developed which implies the earlier results on pattern reproduction and generalizes them to tessellation structures whose state alphabets are arbitrary fields of non-zero characteristic and whose tessellation arrays are arbitrary countable abelian groups. It is also shown that a local transformation can be chosen to produce at a specified time any desired set of “copies” of an initial pattern each multiplied by a specified scalar. We then indicate that connections exist between linear tessellation structures and linear partial differential equations which describe wave propagation by giving an example of a classical form of pattern reproduction.     

Packing triangles in bounded degree graphs

We consider the two problems of finding the maximum number of node disjoint triangles and edge disjoint triangles in an undirected graph. We show that the first (respectively second) problem is polynomially solvable if the maximum degree of the input graph is at most 3 (respectively 4), whereas it is APX-hard for general graphs and NP-hard for planar graphs if the maximum degree is 4 (respectively 5) or more.     

A representation of a C2 interpolant over triangles

A C² piecewise nonic interpolant defined over triangles is derived using the Bernstein-Bézier method. The interpolant can be constructed to require only vertex data (including derivatives) and to have seventh degree polynomial precision.     

On average and highest number of flips in pancake sorting

We are given a stack of pancakes of different sizes and the only allowed operation is to take several pancakes from the top and flip them. The unburnt version requires the pancakes to be sorted by their sizes at the end, while in the burnt version they additionally need to be oriented burnt-side down. We are interested in the largest value of the number of flips needed to sort a stack of $n$ pancakes, both in the unburnt version ($f\left(n\right)$) and in the burnt version ($g\left(n\right)$).We present exact values of $f\left(n\right)$ up to $n=19$ and of $g\left(n\right)$ up to $n=17$ and disprove a conjecture of Cohen and Blum by showing that the burnt stack $?I_{15}$ is not the hardest to sort for $n=15$.We also show that sorting a random stack of $n$ unburnt pancakes can be done with at most $17n/12+O\left(1\right)$ flips on average. The average number of flips of the optimal algorithm for sorting stacks of $n$ burnt pancakes is shown to be between $n+\Omega (n/logn)$ and $7n/4+O\left(1\right)$ and we conjecture that it is $n+\Theta (n/logn)$.Finally we show that sorting the stack $?I_n$ needs at least $?(3n+3)/2?$ flips, which slightly increases the lower bound on $g\left(n\right)$. This bound together with the upper bound for sorting $?I_n$ found by Heydari and Sudborough in 1997 [10] gives the exact number of flips to sort it for $n\equiv 3(mod4)$ and $n\ge 15$.     

Centroidal Voronoi tessellation in universal covering space of manifold surfaces

The centroidal Voronoi tessellation (CVT) has found versatile applications in geometric modeling, computer graphics, and visualization, etc. In this paper, we first extend the concept of CVT from Euclidean space to spherical space and hyperbolic space, and then combine all of them into a unified framework - the CVT in universal covering space. The novel spherical and hyperbolic CVT energy functions are defined, and the relationship between minimizing the energy and the CVT is proved. We also show by our experimental results that both spherical and hyperbolic CVTs have the similar property as their Euclidean counterpart where the sites are uniformly distributed with respect to given density values. As an example of the application, we utilize the CVT in universal covering space to compute uniform partitions and high-quality remeshing results for genus-0, genus-1, and high-genus (genus > 1) surfaces.     

On Quickselect, partial sorting and Multiple Quickselect

We present explicit solutions of a class of recurrences related to the Quickselect algorithm. Thus we are immediately able to solve recurrences arising at the partial sorting problem, which are contained in this class. Furthermore we show how the partial sorting problem is connected to the Multiple Quickselect algorithm and present a method for the calculation of solutions for a class of recurrences related to the Multiple Quickselect algorithm. Further an analysis of an algorithm for sorting a subarray A[r…r+p−1], given the array A[1…n], is provided.     

Efficiently using connectivity information between triangles in a mesh for real-time rendering

Triangle meshes are the most popular standard model used to represent polygonal surfaces. Drawing these meshes as a set of independent triangles involves sending a vast amount of information to the graphics system. Taking advantage of the connectivity information between the triangles in a mesh dramatically diminishes the amount of information the graphics system must handle. Multiresolution Triangle Strips (MTS) represent a triangle mesh as a collection of multiresolution triangles strips. These strips are the basis of both the storage and the rendering stage. The coherence between the extraction of two levels of detail is used in the model in order to decrease the visualisation time.     

Counting triangles in real-world networks using projections

Triangle counting is an important problem in graph mining. Two frequently used metrics in complex network analysis that require the count of triangles are the clustering coefficients and the transitivity ratio of the graph. Triangles have been used successfully in several real-world applications, such as detection of spamming activity, uncovering the hidden thematic structure of the web and link recommendation in online social networks. Furthermore, the count of triangles is a frequently used network statistic in exponential random graph models. However, counting the number of triangles in a graph is computationally expensive. In this paper, we propose the EigenTriangle and EigenTriangleLocal algorithms to estimate the number of triangles in a graph. The efficiency of our algorithms is based on the special spectral properties of real-world networks, which allow us to approximate accurately the number of triangles. We verify the efficacy of our method experimentally in almost 160 experiments using several Web Graphs, social, co-authorship, information, and Internet networks where we obtain significant speedups with respect to a straightforward triangle counting algorithm. Furthermore, we propose an algorithm based on Fast SVD which allows us to apply the core idea of the EigenTriangle algorithm on graphs which do not fit in the main memory. The main idea is a simple node-sampling process according to which node i is selected with probability \fracd_i2m{\frac{d_i}{2m}} where d _i is the degree of node i and m is the total number of edges in the graph. Our theoretical contributions also include a theorem that gives a closed formula for the number of triangles in Kronecker graphs, a model of networks which mimics several properties of real-world networks.     

Ray shooting on triangles in 3-space

We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines inR ³ into points and hyperplanes in five-dimensional projective space (Plücker space). We obtain new results on the following problems:

1. Preprocessn triangles so as to answer efficiently the query: “Given a ray, which is the first triangle hit?” (Ray- shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles.
2. Construct the intersection of two nonconvex polyhedra in an output sensitive way with asubquadratic overhead term.
3. Construct the arrangement ofn intersecting triangles in 3-space in an output-sensitive way, with asubquadratic overhead term.
4. Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra.
5. Preprocessn lines (segments) so as to answer efficiently the query “Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?” (Isotopy problem). If the movement is possible produce an explicit representation of it.