The study of computer algorithms which admit geometric descriptions, and geometric problems arising in association with such algorithms. The two major classes of problems are (a) efficient design of algorithms and data classes using geometric concepts and (b) representation and modelling of curves ...
3
votes
4answers
1k views
Find the area of overlap of two triangles
Suppose we are given two triangles $ABC$ and $DEF$. We can assume nothing about them other than that they are in the same plane. The triangles may or may not overlap. I want to algorithmically ...
2
votes
1answer
72 views
Test if a given point q is a kernel of polygon P
Point $q$ is a kernel of a polygon $P$ if from $q$ we can see all vertices of $P$.
In addition, kernel is a intersection of $N$ half planes formed by edges of polygon.
Proofs of the above ...
0
votes
2answers
509 views
Ellipse fitting methods.
I have set of points and want to fit ellipse to this set.
I have found only function which fits ellipse in least squares sense. In this set of points there are some noise points which should not be ...
2
votes
1answer
222 views
Finding points on ellipse
I have ellipse in 2D. I want to compute fixed number of points on this ellipse with constant angular seperation between those points.
My first idea was to generate line equations from center of the ...
0
votes
0answers
33 views
Approximating a spheroid using spheres
I seek a way to approximate a spheroid using spheres. I guess this is a classic sphere packing problem? I am dealing mostly with prolate spheroids.
I use the definition given here ...
1
vote
1answer
34 views
weighted initial ideal versus lex or graded reverse lex initial ideal
$$
$$
By imposing certain weights $\mathbf{w}$ on the variables, say, of a polynomial ring $k[x_1,\ldots, x_n]$, I read that we may obtain the initial ideal $In_{\mathbf{w}}(I)$ of an ideal $I$ with ...
0
votes
0answers
40 views
using weight vector in M2
Let $R = k[x_1,\ldots, x_n]$ be a polynomial ring and assume $f_i$ and $g_i$ are homogeneous of degree 2, and $h_j$'s are linear forms.
I would like to show that assuming $A = \{f_i + t g_i, h_j\}$ ...
3
votes
1answer
83 views
Determining position at some point in time
I try to solve the following problem.
On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
2
votes
1answer
61 views
Isomorphism of ideals
I have a question related to this post: http://mathoverflow.net/questions/60412/generic-liftings-of-a-regular-sequence-on-the-initial-ideal
Suppose $I$ and $J$ are ideals in $R=k[x_1,\ldots,x_n]$ ...
4
votes
2answers
157 views
+50
Average degree of convex hull vertices in a Delaunay triangulation
Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. ...
2
votes
1answer
102 views
Cutting of the Delaunay triangulation
I am working on terrain rendering tool currently. I have to cut a piece from a given Delaunay triangulation. Suppose following triangulation is given:
The red square depicts area to cut from the ...
1
vote
0answers
80 views
Expected Number of Convex Layers and the expected size of a layer for different distributions
It is well-known that the expected number of vertices on the convex hull of random set of points in the plane distributed uniformly within a $k$-gon is $O(k\log n)$ and within a smooth shape (e.g. a ...
0
votes
1answer
63 views
Wrapping polyhedral of a volumetric mesh
How can I calculate and find the wrapping polyhedral of a mesh which is hexahedral? I mean I have to remove inner elements from my mesh and just have the faces and elements that can be seen from ...
0
votes
1answer
182 views
Visibility and Kernel of Polygon
I have an exercise to a give very rigorous prove to two observations of computation geometry. Obviously there are related. I've tried to prove them and wrote few ideas. Please take a look at them, and ...
1
vote
1answer
68 views
How to find out the control function of a cosine wave with sinusoidal input?
I have a system which is sampling at 100Hz. my input is sinusodial. The output is similar to cosine waveforms with varying frequency. I have no clue how to find out the exact formula to put into the ...
4
votes
0answers
116 views
Convex hull of balls
The convex hull is defined as the smallest convex set containing a set of points. Now we want to generalize it to a set of balls. If these balls have the same radius, then it can be shown that a ball ...
0
votes
0answers
103 views
Difference between Marching Cube Algorithm and Iso-Surfaces?
I have always seen the two ideas together so I am not sure what makes them different...
0
votes
1answer
79 views
What is the X, Y, Z “resolution” of a three-dimensional grid of points?
I came accross a software which requires the X, Y and Z resolution of a three-dimensional grid of points as Integer. What is a "3D grid resolution" and how do I find it?
From what I understand, the ...
1
vote
2answers
93 views
Find outline of $N$ points in a plane
If I have $N$ point coordinates $P_i = ( x_i, \, y_i ) $ and I want to draw the outline connecting only the points on the "outside", what is the algorithm to do this?
This is what I want to do:
...
0
votes
0answers
51 views
Sufficient conditions for “2-sphericity” of orientable triangulated 2d surface in 3d space
Let $T$ be finite set of tetrahedrons in $\mathbb{R}^3$. Let $T$ be tetrahedral complex in a sense that if two tetrahedrons intersect, the intersection is a face of both. Let $\partial T$ consist of ...
0
votes
1answer
85 views
Draw a polygon that satisfies this criterion
Draw a picture of a simple polygon and a set of guards, such that the guards can see every point on every edge of the polygon, but the guards cannot see every point in the interior of the polygon.
I ...
6
votes
2answers
263 views
Tiling pythagorean triples with minimal polyominoes
Given a Pythagorean triple $(a,b,c)$ satisfying $a^2+b^2=c^2$, how to calculate the least number of polyominoes of total squares $c^2$, needed, such that both the square $c^2$ can be build by piecing ...
2
votes
1answer
133 views
Calculating volume of convex polytopes generated by inequalities
I have a set of inequalities, I am looking for a way to compute its volume. More specifically, I would like to compute the ratio of its volume with the volume if some more inequalities were added. I ...
1
vote
1answer
55 views
Polygon: Internal Rays
Suppose I have an arbitrary non-self-intersecting polygon.
I want to generate a list of points which lie on the edges of this polygon according to the following procedure:
I iterate over each edge ...
1
vote
3answers
134 views
Finding a point above the line in $O(\log n)$
I am trying to solve the following problem. So far with no success.
Let $S$ be a set of $n$ points in the plane. Preprocess $S$ so that, given a (non-vertical) line $l$, one can determine whether ...
1
vote
1answer
215 views
Meaning of this 4x4 determinant
Let $p,q,r$ and $s$ be four points on the plane. Moreover, $p,q,r$ are given in clockwise order. My book said that the following determinant is positive if and only if $s$ lies inside the circle ...
1
vote
1answer
91 views
Testing polygon monotonicity
I am looking for an idea of an algorithm for the following problem:
Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not ...
1
vote
1answer
287 views
The dual graph of the triangulation
I study Polygon Triangulation and have an execise.
Prove or disprove: The dual graph of the triangulation of a monotone polygon is always a chain, that is, any node in this graph has degree at ...
2
votes
2answers
338 views
Connecting all points on a plane with shortest path possible
I want to connect N nodes, so all are connected, by connecting each node to their closest neighbors. An image of what I'm looking for is below.
Currently I solve it like this: I add a random node to ...
0
votes
1answer
327 views
Improving Gift Wrapping Algorithm
I am trying to solve taks 2 from exercise 3.4.1 from Computational Geometry in C by Joseph O'Rourke. The task asks to improve Gift Wrapping Algorithm for building convex hull for the set of points.
...
2
votes
2answers
234 views
“Concave hull” - Possible? Feasible? Deterministic?
So there are several questions regarding how to compute the convex hull of a set of points. However, let's say that on inspection the set of points inscribed a star shape. A Convex hull algorithm ...
0
votes
0answers
87 views
Decomposition of multidimensional point set
I am trying to use point sets to define the subdivisions of a multidimensional space and use a hash table to store the subvisions. This approach requires decomposing the multidimensional space into ...
2
votes
0answers
34 views
Terrain tile scale in case of tilted camera
I am working on 3d terrain visualization tool right now. The surface is logically covered with square tiles. This tiling could be visualized as follows:
For some reason I have to know scale of a ...
3
votes
1answer
112 views
Method For Constructing Self Referential Formulas Like Tupper's
Can anyone please explain exactly how formulas like Tupper's self referential formula can be constructed?
I'll like to see the reasoning behind the derivation of such formulas and the steps required ...
1
vote
1answer
97 views
Algorithm for Triangulation Dual Tree
I am looking for algorithm for the following problem.
Given a list of diagonals of a polygon forming a triangulation, with each diagonal specified by counterclockwise indices of the endpoints, ...
1
vote
0answers
50 views
Triangulation of a Convex Polygon [duplicate]
Possible Duplicate:
Explanation/Intuition behind why $C_n$ counts the number of triangulations of a convex $n+2$-gon?
I am interested in counting of how many distinct triangulation are ...
0
votes
0answers
101 views
polygon inside a polygon
i have several point patches lie on different planar faces. then, I obtained enclosing polygons to represent points so that i have several planar polygons (for example A,B,C,D).
when i examine the ...
1
vote
0answers
194 views
differentiation of polygons, having cross borders
I have point data set and I segmented the data into different planar objects. after that, using contouring (convex hull), I obtained the boundary points. Please assume all points relevant to one ...
1
vote
1answer
62 views
Convex Hull in Hierarchy Structure
As a beggining to convex hull algorithms lecturer introduced the structure which it's called "Hierarchy Structure".
Hierarchy Structure: in every given convex hull there is a maximum size convex hull ...
3
votes
3answers
375 views
Studying the envelope of a family of circles.
This is an exercise on page 150 of Cox/Little/O'Shea's Ideal, varieties and algorithms: an introduction to computational algebraic geometry and commutative algebra, 3rd ed.
I get lost in this ...
0
votes
1answer
87 views
How to find a parametrization of a equation and to draw its picture.
I was wondering how to find a parametrization of $(x-t)^2+(y-t^2)^2-t^2=0$, and how to use a software like Mathematica to draw a picture of this equation based on the parametrization.
Thanks in ...
0
votes
1answer
54 views
Prove that there is a set of n points such that a voronoi cell contains n-1 vertices
We need to prove the following claim:
There exists a set of n points such that voronoi cell of one of the
points contains n-1 vertices.
I think in the following case voronoi cell for point C ...
0
votes
0answers
71 views
Does a single Gauss-Seidel iteration lead to unique coordinates?
I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$, and $x,y\in\mathbb{R}^{n\times 2}$ are ...
2
votes
1answer
123 views
Finding the intersections of straight lines
Given a set of lines intersecting the quadrant with $x, y>0$, what are the available algorithms for finding the area below all straight lines (including $y$ and $x$ axis)? In other words, methods ...
0
votes
0answers
78 views
Can 2 parallel lines be discriminated as 'away', 'beside' with respect to 3rd parallel line?
I have nearly parallel several 3D line segments. some line segments locate (blue line) beside to a spefic line segment (black line) and some other (red line) locate away from that line segment. i want ...
0
votes
0answers
104 views
“Way” to decide if points are in a rectangle.
Suppose $P_1=(x_1,y_1)$, $P_2=(x_2,y_2)$ are two points.
Also suppose that we have a rectangle which we just know the value of its sides $a$ and $b$.
I am looking for some kind of formulation which ...
1
vote
1answer
269 views
Convex Hull Algorithms
I have an exercise in Computational Geometry. At first all statements look like very obvious and straightforward and this is misleading. All proofs should be very careful and very rigorous. Please ...
2
votes
2answers
112 views
Did I write the right “expressions”?
$9$. Consider the parametric curve $K\subset R^3$ given by
$$x = (2 + \cos(2s)) \cos(3s)$$
$$y = (2 + \cos(2s)) \sin(3s)$$
$$z = \sin(2s)$$
a) Express the equations of K as polynomial ...
1
vote
2answers
117 views
General Proof Of Intersection Of Two Segments
Sorry for a silly question,
I am trying to prove the fact of intersection of two segments on the plane.
For example, $(d_1,d_2)$ is the first segment, where $d_1$ and $d_2$ are endpoint of the ...
0
votes
1answer
76 views
How to compute this set operation?
Suppose there are two sets (spaces) X and Y. Given N subsets of $X \times Y$: $S_1, \dots, S_N \subseteq X \times Y$. I need to compute the following set $S_X \subseteq X$:
$$
S_X = \{x \in X : ...
