Identifying edges and boundary points – 2D Mesh – Matlab

April 21, 2015 Leave a comment

A triangulation algorithm often gives as output a list of points, and a list of triangle. Each triangle is represented by the indexes of the points which form it. Sometimes we need extra information on the structure of the triangulation, like the list of edges, or the list of boundary points. I will present below two fast algorithms for doing this.

Finding the list of edges is not hard. The idea is to go through each triangle, and extract all edges. The algorithm proposed below creates the adjacency matrix in the following way: for each triangle {[i,j,k]} we set the elements {a_{ij},a_{jk},a_{ik}} (and their symmetric correspondents) to be equal to {1}.

In order to find the points on the boundary (in two dimensions), it is enough to look for the edges which are sides to only one triangle. We can do this using the adjacency matrix. Note that if {A} is the adjacency matrix, then {A^2=(b_{ik})} stores the number of paths of length {2} (two sides) between two points of the triangulation. Note that any edge which is not on the boundary will contain the starting and ending point of two paths of length {2}. If {[i,j,k]} is a triangle such that points {i,j} are on the boundary, then {b_{i,j}=1} (there is one path of length {2} going through {i,k,j}. We also have {a_{i,j} = 1}. Conversely, if {a_{i,j} = 1} and {b_{i,j} = 1} then {i,j} are connected, and there is a unique path of length {2} going from {i} to {j}. Thus, {i,j} is an edge on the boundary. Therefore, we just need to identify the indexes {i} such that there exists {j} with {a_{i,j} b_{i,j} = 1}.

Below are two short Matlab codes doing these two algorithms. I guess they are close to being optimal, since only sparse and vectorized operations are used.

%p is the list of points
%T is the list of triangles, ap is the number of points
%this computes the adjacency matrix
A = min(sparse(T(:,1),T(:,2),1,ap,ap)+sparse(T(:,2),T(:,3),1,ap,ap)+sparse(T(:,3),T(:,1),1,ap,ap),1);
A = min(A+A',1);
% this finds the boundary points, whose indexes are stored in Ibord
B = A^2.*A==1;
Ibord = find(sum(B,2)>0);

Simple triangle mesh – Matlab code

April 20, 2015 Leave a comment

There are cases when you need to define a simple, regular mesh on a nice set, like a triangle, or a polygon. There are software which are capable of creating such meshes, but most of them will require some computation time (Delaunay triangulation, plus optimization, edge swapping, etc.). I propose to you a simple algorithm for defining a mesh on a triangle. Of course, this can be extended to polygons or other cases (I used a variant of it to create a mesh of a spherical surface).

The idea is very simple: start with three points {P_1,P_2,P_3}, and define the (only) initial triangle as {T = [1,\ 2,\ 3]}. Then, at each step, take a triangle {t_i} from the list {T}, add the midpoints of {t_i} to the list of points and replace the triangle {t_i} with the four smaller triangles determined by the vertices and midpoints of {t_i}. This is a basic mesh refining strategy. Thus, in short, we start with a triangle and do a number of mesh refinements, until we reach the desired side-length. Of course, at each step we should be careful not to add the midpoint of an edge two times (once for every neighbouring triangle), but in what follows, I will always remove duplicates by bruteforce in the end (not the most economic solution).

Read more…

Categories: Uncategorized Tags: , ,

Vojtech Jarnik Competition 2015 – Problems Category 2

March 27, 2015 Leave a comment

Problem 1. Let {A} and {B} be two {3 \times 3} matrices with real entries. Prove that

\displaystyle A - (A^{-1}+(B^{-1}-A)^{-1})^{-1} = ABA,

provided all the inverses appearing on the left-hand side of the equality exist.

Problem 2. Determine all pairs {(n,m)} of positive integers satisfying the equation

\displaystyle 5^n = 6m^2+1.

Problem 3. Determine the set of real values {x} for which the following series converges, and find its sum:

\displaystyle \sum_{n=1}^\infty \left( \sum_{k_i \geq 0, k_1+2k_2+...+nk_n = n} \frac{(k_1+...+k_n)!}{k_1!...k_n!} x^{k_1+...+k_n}\right).

Problem 4. Find all continuously differentiable functions {f : \Bbb{R} \rightarrow \Bbb{R}}, such that for every {a \geq 0} the following relation holds:

\displaystyle \int_{D(a)} xf\left( \frac{ay}{\sqrt{x^2+y^2}}\right) dxdydz = \frac{\pi a^3}{8}(f(a)+\sin a -1),

where {D(a) = \left\{ (x,y,z) : x^2+y^2+z^2 \leq a^2,\ |y| \leq \frac{x}{\sqrt{3}}\right\}}

Vojtech Jarnik Competition 2015 – Category 1 Problems

March 27, 2015 Leave a comment

Problem 1. Let {f:\Bbb{R} \rightarrow \Bbb{R}} be differentiable on {\Bbb{R}}. Prove that there exists {x \in [0,1]} such that

\displaystyle \frac{4}{\pi}(f(1)-f(0))=(1+x^2)f'(x).

Problem 2. Consider the infinite chessboard whose rows and columns are indexed by positive integers. Is it possible to put a single positive rational number into each cell of the chessboard so that each positive rational number appears exactly once and the sum of every row and of every column is finite?

Problem 3. Let {P(x)=x^{2015}-2x^{2014}+1} and {Q(x) = x^{2015}-2x^{2014}-1}. Determine for each of the polynomials {P} and {Q} whether it is a divisor of some nonzero polynomial {c_0+c_1x+...+c_nx^n} whose coefficients {c_i} are all in the set {\{1,-1\}}.

Problem 4. Let {m} be a positive integer and let {p} be a prime divisor of {m}. Suppose that the complex polynomial {a_0+a_1x+...+a_nx^n} with {n< \displaystyle \frac{p}{p-1}\varphi(m)} and {a_n \neq 0} is divisible by the cyclotomic polynomial {\Phi_m(x)}. Prove that there at least {p} non-zero coefficients {a_i}.

The cyclotomic polynomial {\Phi_m(x)} is the monic polynomial whose roots are the {m}-th primitive complex roots of unity. Euler’s totient function {\varphi(m)} denotes the number of positive integers less than or eual to {m} which are coprime to {m}.

Categories: Olympiad Tags: , ,

Seemous 2015 Problem 1

March 11, 2015 1 comment

Problem 1. Prove that for every {x \in (0,1)} the following inequality holds:

\displaystyle \int_0^1 \sqrt{1+\cos^2 y}dy > \sqrt{x^2+\sin^2 x}.

Read more…

Seemous 2015 Problems

March 11, 2015 Leave a comment

Problem 1. Prove that for every {x \in (0,1)} the following inequality holds:

\displaystyle \int_0^1 \sqrt{1+\cos^2 y}dy > \sqrt{x^2+\sin^2 x}.

Problem 2. For any positive integer {n}, let the functions {f_n : \Bbb{R} \rightarrow \Bbb{R}} be defined by {f_{n+1}(x)=f_1(f_n(x))}, where {f_1(x)=3x-4x^3}. Solve the equation {f_n(x)=0}.

Problem 3. For an integer {n>2}, let {A,B,C,D \in \mathcal{M}_n(\Bbb{R})} be matrices satisfying:

\displaystyle AC-BD = I_n,

\displaystyle AD+BC = O_n,

where {I_n} is the identity matrix and {O_n} is the zero matrix in {\mathcal{M}_n(\Bbb{R})}.

Prove that:

  • (a) {CA-DB = I_n} and {DA+CB = O_n}.
  • (b) {\det(AC) \geq 0} and {(-1)^n \det(BD) \geq 0}.

Problem 4. Let {I\subset \Bbb{R}} be an open interval which contains {0} and {f: I \rightarrow \Bbb{R}} be a function of class {C^{2016}(I)} such that {f(0)=0, f'(0)=1, f''(0) = ... = f^{(2015)}(0)=0,\ f^{(2016)}(0)<0}.

  • (i) Prove that there exists {\delta>0} such that {0<f(x)<x} for {x \in (0,\delta)}.
  • (ii) With {\delta} determined at (i) define the sequence {(a_n)} by

    \displaystyle a_1 = \frac{\delta}{2},\ a_{n+2}=f(a_n),\ n \geq 1.

    Study the convergence of the series {\displaystyle \sum_{n=1}^\infty a_n^r} for {r \in \Bbb{R}}.


Read more…

Categories: Olympiad Tags: , , ,

Putnam 2014 Problems

December 8, 2014 Leave a comment

A1. Prove that every nonzero coefficient of the Taylor series of {(1-x+x^2)e^x} about {x=0} is a rational number whose numerator (in lowest terms) is either {1} or a prime number.

A2. Let {A} be the {n\times n} matrix whose entry in the {i}-th row and {j}-th column is

\displaystyle \frac1{\min(i,j)}

for {1\le i,j\le n.} Compute {\det(A).}

A3. Let {a_0=5/2} and {a_k=a_{k-1}^2-2} for {k\ge 1.} Compute

\displaystyle \prod_{k=0}^{\infty}\left(1-\frac1{a_k}\right)

in closed form.

A4. Suppose {X} is a random variable that takes on only nonnegative integer values, with {E[X]=1,} {E[X^2]=2,} and {E[X^3]=5.} (Here {E[Y]} denotes the expectation of the random variable {Y.}) Determine the smallest possible value of the probability of the event {X=0.}

A5. Let {P_n(x)=1+2x+3x^2+\cdots+nx^{n-1}.} Prove that the polynomials {P_j(x)} and {P_k(x)} are relatively prime for all positive integers {j} and {k} with {j\ne k.}

A6. Let {n} be a positive integer. What is the largest {k} for which there exist {n\times n} matrices {M_1,\dots,M_k} and {N_1,\dots,N_k} with real entries such that for all {i} and {j,} the matrix product {M_iN_j} has a zero entry somewhere on its diagonal if and only if {i\ne j?}

B1. A base {1} over-expansion of a positive integer {N} is an expression of the form {N=d_k10^k+d_{k-1}10^{k-1}+\cdots+d_0 10^0} with {d_k\ne 0} and {d_i\in\{0,1,2,\dots,10\}} for all {i.} For instance, the integer {N=10} has two base 10 over-expansions: {10=10\cdot 10^0} and the usual base 10 expansion {10=1\cdot 10^1+0\cdot 10^0.} Which positive integers have a unique base 10 over-expansion?

B2. Suppose that {f} is a function on the interval {[1,3]} such that {-1\le f(x)\le 1} for all {x} and {\displaystyle \int_1^3f(x)\,dx=0.} How large can {\displaystyle\int_1^3\frac{f(x)}x\,dx} be?

B3. Let {A} be an {m\times n} matrix with rational entries. Suppose that there are at least {m+n} distinct prime numbers among the absolute values of the entries of {A.} Show that the rank of {A} is at least {2.}

B4. Show that for each positive integer {n,} all the roots of the polynomial

\displaystyle \sum_{k=0}^n 2^{k(n-k)}x^k

are real numbers.

B5. In the 75th Annual Putnam Games, participants compete at mathematical games. Patniss and Keeta play a game in which they take turns choosing an element from the group of invertible {n\times n} matrices with entries in the field {\mathbb{Z}/p\mathbb{Z}} of integers modulo {p,} where {n} is a fixed positive integer and {p} is a fixed prime number. The rules of the game are:

(1) A player cannot choose an element that has been chosen by either player on any previous turn.

(2) A player can only choose an element that commutes with all previously chosen elements.

(3) A player who cannot choose an element on his/her turn loses the game.

Patniss takes the first turn. Which player has a winning strategy?

B6. Let {f:[0,1]\rightarrow\mathbb{R}} be a function for which there exists a constant {K>0} such that {|f(x)-f(y)|\le K|x-y|} for all {x,y\in [0,1].} Suppose also that for each rational number {r\in [0,1],} there exist integers {a} and {b} such that {f(r)=a+br.} Prove that there exist finitely many intervals {I_1,\dots,I_n} such that {f} is a linear function on each {I_i} and {[0,1]=\bigcup_{i=1}^nI_i.}

Categories: Olympiad Tags: ,

Get every new post delivered to your Inbox.

Join 359 other followers

%d bloggers like this: