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 ...

learn more… | top users | synonyms

6
votes
2answers
53 views

Simplest graph that is not a segment intersection graph

Given a finite collection $S=\{s_1,s_2,\ldots,s_n\}$ of straight-line segments in the plane, their intersection graph $G(S)$ is a graph that contains a vertex $v_i$ for each segment $s_i\in S$, and an ...
2
votes
2answers
48 views

How to make sure that a given set of points lie on the boundary of a possible square?

Given a set of integral coordinates , check whether all the points given lie on side of a possible square such that axis of the square so formed lie parallel to both X-axis and Y-axis . Suppose ...
2
votes
2answers
76 views

Polytope parametrization

How one could parametrize a convex polytope? By parametrization I mean something like in multiple integrals, when to integrate over an area one can integrate over one variable in an interval $[l,r]$ ...
2
votes
2answers
226 views

Given two sets of vectors, how do I find a change of basis that will convert one set to another?

Given two sets of dimension $n$ vectors $\lbrace v_1 , v_2 , \ldots , v_m \rbrace$, $\lbrace u_1, u_2, \ldots , u_m \rbrace$, where $m > n$, is there a computational method (in particular, using ...
1
vote
2answers
30 views

Determinant (computational geometry)

Let p=(px,py),q=(qx,qy), and r=(rx,ry).Show that the sign of the determinant |1 px py| D=|1 qx qy| |1 rx ry| determines whether a point r lies to the ...
1
vote
2answers
65 views

What is the equation stands for in geometry(intuitively)?

I am writing a bilinear interpolation method. This method can be abstract by solve the equation A*x = b, A is a 4x4 matrix below: $A=\begin{pmatrix} 1 &x_1 &y_1 &x_1y_1\\ 1 ...
0
votes
2answers
37 views

Room for computational geometry in advanced algorithms course

I am currently putting together an independent study in advanced algorithms and because of my interest in (computational) geometry, wanted to include as many interesting algorithms from this field as ...
0
votes
1answer
43 views

Using cartesian coordinates how to get the segment overlapping two lines/segments?

There must be an algorithm to find the coordinates of the segment overlapping (fully or partially) two lines/segments but my googling does not produce any significant result. Maybe I don't use the ...
0
votes
1answer
231 views

Determining the direct and transverse tangent lines for two non-overlapping ellipses

I am trying to determine the direct and transverse lines for two non-overlapping ellipses. I specifically mean that the two ellipses are totally separated from each other with no shared regions. I ...
0
votes
1answer
107 views

Convex hull questions

Suppose I am in D-dimensional space, e.g. D=2. What is the minimum number of points to create a valid convex hull? If D = 2, would I need 3 points to create a convex hull (i.e. to form a triangle)? ...
0
votes
1answer
64 views

Understanding the Wolfram Demonstration “Distance of a Point to a Polygon”

I've recently came across a neat Wolfram Demonstration script by Jaime Rangel-Mondragon that calculates the minimum distance from a point to an arbitrary convex or non-convex polygon: ...
0
votes
1answer
69 views

Generating Vectors under Constraints on 1 and 2 norm

Update: I left out some important information in my previous description... I am actually dealing with a special problem, which is better described as follows: Given user-specified parameters ...
0
votes
1answer
113 views

Steepest slope gradient of a vertical plane

I know the steepest slope gradient (Azimuth) of a 3D plane can be obtained by projecting normal vector onto XY Plane. So, when the plane is slant, the steepest gradient will be a some value. ...
0
votes
1answer
138 views

Analytic Intersection of Objects Located on a 3D Grid's Vertices

I previously posted this question on stackoverflow, but it's really more of a mathematical question. I have reworked the question for presentation here. I have a regular 3D unit cubic grid of ...
0
votes
1answer
96 views

What are algorithms or approaches to find a convex hull on higher dimensions?

I have some background in 2D computational geometry and understand how to find a convex hull in 2D. Now I'm looking at a set of vectors with 20-some components and want to find the convex hull on ...
-1
votes
1answer
101 views

How to get the third point coordinates in isosceles triangle?

Isosceles triangle $ABC$ $AB = AC = d_1$ $BC = d_2$ $A = (x_1, y_1)$ $B = (x_2, y_2)$ $C = (x_3, y_3)$ $\angle BAC = \phi$ $\angle ABC =\angle ACB = \theta$ I want an equation for $x_3$ and $y_3$ ...