TADM2E 5.11 - Revision history

Matt: Undo revision 1082 by FuckMatt (talk)

2020-08-01T00:52:24Z

Undo revision 1082 by FuckMatt (talk)

FuckMatt: Redirected page to UNTV

2020-07-31T10:12:39Z

Redirected page to UNTV

Ysag at 14:09, 16 February 2016

2016-02-16T14:09:34Z

Algowikiadmin: Recovering wiki

2014-09-11T18:23:22Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:49Z

Recovering wiki

New page

The algorithm Which I am presenting requires a HUGE amount of memory.. but gives O(n).. for "n" triangles

Consider the representation of data, the same way as in the war story.
i.e a number vertices, and Triangles mentioned as a set of 3 vertices.
We will keep one adjacency Matrix. This matrix will tell whether or
not an edge exists. If an edge exists, the matrix contains the pointer to
the element representing the edge. Initially the Matrix is empty and have no
idea about the edges.
We will maintain an array of edges.
Every element of this array will basically point to a list of triangles, that contain that edge.
(This is similar to an adjacency list, where every vertex maintains a list of adjacent vertices).
For example:
e1 -> T4 (Edge 1 is contained in Triangle 4)
e2 -> T3 (Edge 2 is contained in Triangle 3)..
Now when we read a triangle, for every edge we check if that edge element is present
in the Matrix. If so, the Matrix contains the pointer to the edge element.
This edge element can be present in only 1 other Triangle. So we immediately get
The triangle sharing the edge.
This way we can get all adjacent Triangles (Max 3, one for each edge) for every triangle
in constant time. For n triangles, this gives O(n) running time.

← Older revision		Revision as of 10:12, 31 July 2020
Line 1:		Line 1:
−	~~The algorithm Which I am presenting requires a HUGE amount of memory.. but gives O(n).. for "n" triangles~~	+	#REDIRECT [[UNTV]]
−
−
−	~~Consider the representation of data, the same way as in the war story.~~
−	~~i.e a number vertices, and Triangles mentioned as a set of 3 vertices.~~
−	~~We will keep one adjacency Matrix. This matrix will tell whether or~~
−	~~not an edge exists. If an edge exists, the matrix contains the pointer to~~
−	~~the element representing the edge. Initially the Matrix is empty and have no~~
−	~~idea about the edges.~~
−	~~We will maintain an array of edges.~~
−	~~Every element of this array will basically point to a list of triangles, that contain that edge.~~
−	~~(This is similar to an adjacency list, where every vertex maintains a list of adjacent vertices).~~
−	~~For example:~~
−	~~e1 -> T4 (Edge 1 is contained in Triangle 4)~~
−	~~e2 -> T3 (Edge 2 is contained in Triangle 3)..~~
−	~~Now when we read a triangle, for every edge we check if that edge element is present~~
−	~~in the Matrix. If so, the Matrix contains the pointer to the edge element.~~
−	~~This edge element can be present in only 1 other Triangle. So we immediately get~~
−	~~The triangle sharing the edge.~~
−	~~This way we can get all adjacent Triangles (Max 3, one for each edge) for every triangle~~
−	~~in constant time. For n triangles, this gives O(n) running time.~~
−
−
−	~~<h3> Another solution using a hash-table </h3>~~
−	~~This solution is similar to the above, but it uses an array of hashtables to maintain the mapping from seen edges to triangles.~~
−	The key observation is that any edge in the triangulation can be seen at most twice. When we see the <math>k^{th}</math> triangle <math>(x_{k1}, x_{k2}, x_{k3})</math>, we take each edge <math>(x_{ki}, x_{kj})</math> such that <math>x_{ki} \lt x_{kj}</math> (i.e., in the sorted order of vertex numbers in triangle <math>k</math>), and do the following (H is the array of <math>m</math> hashtables, where <math>m</math> is the number of vertices in the triangulation. Note that this can easily also be made a hashtable of pointers to hashtables to save space)
−
−	* If the hashtable for <math>x_{ki}</math> (<math>H[~~x_{ki}]</math>) doesn't exist yet, create and initialize it.~~
−	* Check if an item with key <math>x_{kj}</math> exists in <math>H[x_{ki}]</math>.
−	** If not, this is the first time we are seeing this edge <math>(x_{ki}, x_{kj})</math>, so add <math>k</math> under the key <math>x_{kj}</math> in <math>H[~~x_{ki}~~]~~</math> and continue.~~
−	** If yes, retrieve the element (say with value <math>l</math>), add an edge from <math>k</math> to <math>l</math> in the dual graph and (optionally) delete the item from <math>H[x_{ki}]~~</math>.~~
−
−
−	We repeat the above for each of the three edges of each triangle in the triangulation. Since the operations above can be implemented to be run in (amortized) constant time, and we consider no more than <math>3n</math>, <math>n</math> being the number of triangles in the triangulation, the algorithm runs in <math>O(n)</math> time.

← Older revision		Revision as of 14:09, 16 February 2016
Line 20:		Line 20:
	This way we can get all adjacent Triangles (Max 3, one for each edge) for every triangle		This way we can get all adjacent Triangles (Max 3, one for each edge) for every triangle
	in constant time. For n triangles, this gives O(n) running time.		in constant time. For n triangles, this gives O(n) running time.
		+
		+
		+	<h3> Another solution using a hash-table </h3>
		+	This solution is similar to the above, but it uses an array of hashtables to maintain the mapping from seen edges to triangles.
		+	The key observation is that any edge in the triangulation can be seen at most twice. When we see the <math>k^{th}</math> triangle <math>(x_{k1}, x_{k2}, x_{k3})</math>, we take each edge <math>(x_{ki}, x_{kj})</math> such that <math>x_{ki} \lt x_{kj}</math> (i.e., in the sorted order of vertex numbers in triangle <math>k</math>), and do the following (H is the array of <math>m</math> hashtables, where <math>m</math> is the number of vertices in the triangulation. Note that this can easily also be made a hashtable of pointers to hashtables to save space)
		+
		+	* If the hashtable for <math>x_{ki}</math> (<math>H[x_{ki}]</math>) doesn't exist yet, create and initialize it.
		+	* Check if an item with key <math>x_{kj}</math> exists in <math>H[x_{ki}]</math>.
		+	** If not, this is the first time we are seeing this edge <math>(x_{ki}, x_{kj})</math>, so add <math>k</math> under the key <math>x_{kj}</math> in <math>H[x_{ki}]</math> and continue.
		+	** If yes, retrieve the element (say with value <math>l</math>), add an edge from <math>k</math> to <math>l</math> in the dual graph and (optionally) delete the item from <math>H[x_{ki}]</math>.
		+
		+
		+	We repeat the above for each of the three edges of each triangle in the triangulation. Since the operations above can be implemented to be run in (amortized) constant time, and we consider no more than <math>3n</math>, <math>n</math> being the number of triangles in the triangulation, the algorithm runs in <math>O(n)</math> time.

← Older revision		Revision as of 00:52, 1 August 2020
Line 1:		Line 1:
−	~~#REDIRECT~~ [[~~UNTV~~]]	+	The algorithm Which I am presenting requires a HUGE amount of memory.. but gives O(n).. for "n" triangles
		+
		+
		+	Consider the representation of data, the same way as in the war story.
		+	i.e a number vertices, and Triangles mentioned as a set of 3 vertices.
		+	We will keep one adjacency Matrix. This matrix will tell whether or
		+	not an edge exists. If an edge exists, the matrix contains the pointer to
		+	the element representing the edge. Initially the Matrix is empty and have no
		+	idea about the edges.
		+	We will maintain an array of edges.
		+	Every element of this array will basically point to a list of triangles, that contain that edge.
		+	(This is similar to an adjacency list, where every vertex maintains a list of adjacent vertices).
		+	For example:
		+	e1 -> T4 (Edge 1 is contained in Triangle 4)
		+	e2 -> T3 (Edge 2 is contained in Triangle 3)..
		+	Now when we read a triangle, for every edge we check if that edge element is present
		+	in the Matrix. If so, the Matrix contains the pointer to the edge element.
		+	This edge element can be present in only 1 other Triangle. So we immediately get
		+	The triangle sharing the edge.
		+	This way we can get all adjacent Triangles (Max 3, one for each edge) for every triangle
		+	in constant time. For n triangles, this gives O(n) running time.
		+
		+
		+	<h3> Another solution using a hash-table </h3>
		+	This solution is similar to the above, but it uses an array of hashtables to maintain the mapping from seen edges to triangles.
		+	The key observation is that any edge in the triangulation can be seen at most twice. When we see the <math>k^{th}</math> triangle <math>(x_{k1}, x_{k2}, x_{k3})</math>, we take each edge <math>(x_{ki}, x_{kj})</math> such that <math>x_{ki} \lt x_{kj}</math> (i.e., in the sorted order of vertex numbers in triangle <math>k</math>), and do the following (H is the array of <math>m</math> hashtables, where <math>m</math> is the number of vertices in the triangulation. Note that this can easily also be made a hashtable of pointers to hashtables to save space)
		+
		+	* If the hashtable for <math>x_{ki}</math> (<math>H[x_{ki}]</math>) doesn't exist yet, create and initialize it.
		+	* Check if an item with key <math>x_{kj}</math> exists in <math>H[x_{ki}]</math>.
		+	** If not, this is the first time we are seeing this edge <math>(x_{ki}, x_{kj})</math>, so add <math>k</math> under the key <math>x_{kj}</math> in <math>H[x_{ki}]</math> and continue.
		+	** If yes, retrieve the element (say with value <math>l</math>), add an edge from <math>k</math> to <math>l</math> in the dual graph and (optionally) delete the item from <math>H[x_{ki}]</math>.
		+
		+
		+	We repeat the above for each of the three edges of each triangle in the triangulation. Since the operations above can be implemented to be run in (amortized) constant time, and we consider no more than <math>3n</math>, <math>n</math> being the number of triangles in the triangulation, the algorithm runs in <math>O(n)</math> time.

@@ Line 1: / Line 1: @@
-The algorithm Which I am presenting requires a HUGE amount of memory.. but gives O(n).. for &quot;n&quot; triangles
+The algorithm Which I am presenting requires a HUGE amount of memory.. but gives O(n).. for "n" triangles
@@ Line 12: / Line 12: @@
    (This is similar to an adjacency list, where every vertex maintains a list of adjacent vertices).
    For example:
-    e1 -&gt; T4   (Edge 1 is contained in Triangle 4)
+    e1 -> T4   (Edge 1 is contained in Triangle 4)
-    e2 -&gt; T3   (Edge 2 is contained in Triangle 3)..
+    e2 -> T3   (Edge 2 is contained in Triangle 3)..
    Now when we read a triangle, for every edge we check if that edge element is present
    in the Matrix. If so, the Matrix contains the pointer to the edge element.