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

-1
votes
3answers
33 views

Obtaining the four corner coordinates of a square from the center point.

I'm trying to get the corner coordinates of a Square (NOTE, always a square) problematically. (EX: With a formula) and I'm having a hard time adding this into my computer application. Here's an ...
6
votes
2answers
69 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 ...
3
votes
2answers
58 views

Box-Counting Dimension with finite resolution

Does the method of determining dimension of a shape via the Box-Counting dimension (Minkowski–Bouligand dimension) have to be performed on fractals (objects that look the same at all scales), or can ...
2
votes
2answers
63 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
111 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]$ ...
1
vote
2answers
157 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
66 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
38 views

differentiating an integral with respect to a variable which also affects the region of integration

I am considering taking the derivative of the function $$F(\mathbb{x_1},\mathbb{x_2},\mathbb{x_3}) = \displaystyle \int_{V_1} ||x-\mathbb{x_1}||\phi(x)\,dx + \int_{V_2} ||x-\mathbb{x_2}||\phi(x)\,dx ...
0
votes
2answers
43 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 ...
6
votes
1answer
212 views

How to determine surface from given normal vectors and their distance on that surface

Situation: We have a bendable, non-stretchable surface, like a piece of cloth, with a regular grid on it. Unknown manipulation of the surface is done while preserving it's structure We recieve 3 ...
4
votes
1answer
116 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
4
votes
1answer
218 views

Dirichlet's approximation theorem (simultaneous version): proof via Minkowski's theorem

There is a proof of the Dirichlet's approximation theorem based on Minkowski's theorem. The proof is given on wikipedia (http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem) and it is ...
3
votes
1answer
93 views

Computing with graphs in surfaces

I am currently working on a research project involving a polynomial defined for graphs in surfaces, similar to the Tutte polynomial, except with terms accounting for the embedding. At the moment, it ...
2
votes
1answer
46 views

Bounding Sphere for Two Hyperrectangles

Please see the image for best illustration of the task. I have two hyperrectangles, $\text{R1}$ and $\text{R2}$, whose exact location and size is arbitrary. Now, my task is to construct a bounding ...
2
votes
1answer
95 views

Algorithm to compute whether a stabbing line exists for a set of line segments

Let $S$ be a set of n segments in the plane. A line $L$ that intersects all segments of $S$ is called a traversal or stabber of $S$. Give an $\mathcal{O}(n^2)$ algorithm to decide if a stabber for $S$ ...
2
votes
1answer
162 views

Modify the closest-pair algorithm to use the $L_\infty$ distance.

I'm trying to understand the closest pair of points problem. I am beginning to understand the two-dimensional case from a question a user posted some years ago. I'll link it in case someone wants to ...
2
votes
1answer
82 views

A method to test for uniform distribution over a convex polytope

Assuming I have a convex polytope defined as the intersection of $Ax=b$ and $x>0$ and I have a way to sample points from this object, is there a way I can test for uniformity of these sampled ...
1
vote
1answer
24 views

How to find the closest line to two segments?

I have two segments in 2D space, defined by their endpoint x and y coordinates. How can I find a best-fit line using vector algebra (formally, that minimizes the integral of square-distance from it to ...
1
vote
1answer
61 views

Prove that volume of a ball in a polytope is very small

An exercise in a book asks to prove that for a bounded convex polytope $P\subseteq\mathbb{R}^n$ defined as an intersection of $k$ closed halfspaces and for a unit ball $B^n$ contained in $P$ the ...
1
vote
1answer
70 views

How to test for a polygon witn n vertices if it's nonintersecting polygon or not?

How can you design an algorithm to know if an n-vertex polygon nonintersecting ? On what criteria is the test going to be
1
vote
1answer
82 views

Find equation of line without using division

I need an algorithm to find equation of a line without using division. Given a line by two points on it, with coordinates: $(x_1, y_1),\ (x_2, y_2)$. We can simply get the line equation by the ...
1
vote
1answer
60 views

Convex Combination of Disks

We can define a closed disk $D$ with center $c$ and radius $r$ as the set of points $x$ satisfying $f(x) \le 1$ where $f(x) = \frac1{r^2}\lVert x-c \rVert^2$. Now take two disks $D_0,\,D_1$ with ...
0
votes
1answer
16 views

Voronoi diagram of a set of vertices of a mesh.

i have a triangulated mesh. I have some vertices which are part of the vertices of the mesh. Is there any algorithm to compute the voronoi diagram of these set of vertices. The triangulated mesh ...
0
votes
1answer
27 views

How do I place two points on two axis-aligned line segments such that they have given Euclidean distance l?

This is my problem: I am given two axis aligned line segments $l_1$ and $l_2$ of finite length and a distance $l$. How do I find points $p_1 \in l_1$ and $p_2 \in l_2$, such that $||p_1-p_2||_2 = l$? ...
0
votes
1answer
36 views

Finding other two vertices of a triangle from centroid and one vertex?

I am working on some gesture recognition for my game and I want to find if a point is inside the triangle created by the user or not. For that I need three vertices. Currently I am using the '$1 ...
0
votes
1answer
74 views

Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or mathoverflow. You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be inside ...
0
votes
1answer
36 views

Visible objects from a point in a polygon with holes in 2d

The problem is the following: Given a polygon P with h holes/objects and a point c inside P but outside the holes/objects. P has n given vertices and each hole/object h has 4 vertices (the ...
0
votes
1answer
167 views

Use of Delaunay Triangulation and Voronoi Diagram to find alpha shape using Edelsbrunner's algorithm

I am learning how to find the shape of a set of points in 2-D. I understand that Alpha Shape method is a good way to find the shape of a set of points. Alpha Shape was originally introduced by H. ...
0
votes
1answer
81 views

Point location( planar subdivision)

Show that, given a planar subdivision S with n vertices and edges and a query point q, the face of S containing q can be computed in time O(n). Assume that S is given in a doubly-connected edge list
0
votes
1answer
16 views

Computing the Center of Gravity of the Unit Cube + Halfspace

Consider the unit hypercube in $\mathbb{R}^N$. $\mathcal{P} = \{\mathbf{x} ~| ~x_i \in [0,1] \text{ for } i=1,\ldots,N \}$ and a half-space which intersects the unit cube: $\mathcal{H} = ...
0
votes
1answer
30 views

Geometry (Convex Polygons)

Let P be a set of points in the plane. Let P1 be the convex polygon whose vertices are points from P and that contains all points in P. Prove that this polygon P1 is uniquely defined, and that it is ...
0
votes
1answer
44 views

Divide set of points by a plane so sum of distances of points on either side of plane is equal

I have a finite set of points A and another point C. I would like to compute a vector N so that the plane defined by C (point on plane) and N (normal of plane) divides all points in A with the sum of ...
0
votes
1answer
123 views

Term For Rotating 3d Vectors About a Pivot Point

What is the term for Rotating a 3d Vector about another 3d Vector (Pivot Point)? For example; if I want to move X distance from one point towards another point - the mathematical term for this ...
0
votes
1answer
120 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
186 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
78 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
71 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
162 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 ...
-1
votes
1answer
151 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 ...
0
votes
0answers
21 views

Existence objective function given optimality regions

Let $I$ and $X$ be finite, nonempty sets, and denote by $\Delta(X)$ the set of probability measures on $(X,2^X)$. Suppose that for each $i \in I$, we are given a subset $M_i \subseteq \Delta(X)$ of ...
0
votes
0answers
52 views

Data structure issues with incremental Delaunay triangulation

I am implementing the incremental algorithm of Delaunay triangulation with a data structure based on Faces (triangles): 3 vertex indices and 3 Neighbor indices. The issue I have is that the structure ...
0
votes
0answers
39 views

Is there a way to compute the empty area between a group of touching polygons?

Given a bunch of convex polygons layed out like a house truss, is there a way to compute the empty area, or get a polygon for each of those "holes" between the polygons? I tried starting from any ...
0
votes
0answers
109 views

Estimating the geometric shape of a point cloud without using the vertex information

Consider a point cloud format that describes 3D point clouds by vertices, triangle labels and normal vectors. If we miss the vertex information, is it possible to retrieve the lost data by triangle ...
0
votes
0answers
127 views

Find vertex of a parallelogram/parallelepiped/parallelotope with minimum distance to a point

Suppose you have a parallelogram and a point. It's easy to tell which of the parallelogram's vertices is closest to the point (Euclidean distance) by checking the distance for every vertex - but this ...
0
votes
0answers
38 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
0
votes
0answers
71 views

transformation function using genetic programming

If I have a set of points in two spaces, say set $A$ contains 50 points and set $B$ contains 50 points. I have to find a transformation function such that if I transform the points in set $A$ using ...
0
votes
0answers
70 views

Plot randomly oriented gaussian kernel

I would like to plot with scipy randomly oriented gaussian kernels. For a gaussian kernel along x and y axis (with an angle 0 w.r.t. coordinate system), I simply plot function ...