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

2
votes
2answers
216 views

Flood algorithm - find polygon containing a given point.

I have some code that represents a set of a set of interconnected line segments in 2D, in pseudo-code it'd be like this: ...
2
votes
2answers
66 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]$ ...
3
votes
0answers
76 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 ...
1
vote
0answers
32 views

Geometric accuracy analysis of 2d rectangular models

I have reconstructed set of rectangular objects lie on a 2D plane (for ex. ABCD). All these objects are in a one coordinate system. On the other hand, I have reference models for all of them ...
5
votes
0answers
70 views

Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
1
vote
1answer
95 views

Calculate base and coefficient for power curve through 3 non-linear points

I have a formula that takes a 0-based bounded single dimensional input and transforms it to a specific power curve. EDIT This is single dimensional. There is no $y$. In the image, I'm showing how ...
3
votes
1answer
119 views

Poisson point process (PPP) and Voronoi cells

Say we have a homogeneous PPP with rate $\lambda$ in the 2-D plane $\mathbb R^2$. In one realization of the PPP we get the points $\phi=\{x_1,x_2,...,x_i,...\}$. Now we generate the Voronoi cells ...
2
votes
0answers
64 views

Higher Order Voronoi Diagram of a Poisson Point Process: What do we know?

This question is looking for probabilistic results of the Voronoi diagrams of 2-D space when the points are distributed by a homogeneous Poisson point process. The results can be the distribution of ...
0
votes
1answer
93 views

Circumsphere of a tetrahedron undefined?

I am trying to find 3D alpha shapes from my data-set. In doing so, I am keeping only those tetrahedra that have circumradius below a certain threshold. However, while finding the circumradius of the ...
1
vote
0answers
36 views

Background required for Computational Geometry

I am hoping to enroll in Computational Geometry course this spring. This was the textbook used for the course in the past. I am trying to figure out if I have required math background for this ...
0
votes
1answer
70 views

Problem while constructing Delaunay triangulation

At the moment I'm implementing an algorithm to construct a Delaunay triangulation for a set of points. I'm using the algorithm described in Computational Geometry: Algorithms and Applications. The ...
2
votes
0answers
47 views

Generalization of Minkowski's theorem

I would like to prove a generalized version of the Minkowski's theorem, but I don't quite know how to do it. Here is what I would like to prove: Let $X\subset \mathbb{R}^d$ is convex, symmetric ...
2
votes
1answer
55 views

Reference for important results in linkage theory and their proofs

Are there books or lecture notes that comprehensively introduce the (geometric/topological) theory of mechanical linkages, as well as important results and their proofs? For instance, Kempe's ...
1
vote
0answers
68 views

Orthogonal 4-cut of a convex polygon

Given a convex polygon with N vertices I need to cut it into four equal area parts with two straight orthogonal cuts. I feel that I have all the necessary pieces to solve this puzzle, but I can't put ...
4
votes
0answers
96 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 ...
1
vote
1answer
53 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 ...
4
votes
2answers
106 views

Convex sets: a hint on how to solve a problem

Could anyone give me a hint on how to solve the following problem? Let $X_1, \dots, X_{d+1}$ be some finite sets in $\mathbb{R}^d$, such that the origin lies in ${\rm conv}(X_i)$ for all $i \in \{1, ...
0
votes
0answers
16 views

Chain of transformations -> continuous

Transformation $A_t$ rotates point $p(t)$ for angle $d\phi(t)$ around the axis $n(t)$ anchored at point $r(t)$ and finally displaces it for $r'(t) dt$. Point is now $p(t + dt)$. More specifically in ...
1
vote
1answer
100 views

3D Convex Hull and The Gift Wrapping Principle

I am currently trying to implement a 3D convex hull algorithm that is based on the paper Convex Hulls of Finite Sets of Points in Two and Three Dimensions by F.P. Preparata and S.J. Hong, but I’ve run ...
0
votes
0answers
77 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 ...
2
votes
1answer
107 views

How to extract the indeterminates from a set of polynomial?

I am a biologist and I am facing a huge problem. I would like to extract the indeterminates of a set of polynomials, for example, I have: $f_{1} = \{\\x_{3}^{2} + x_{1}*x_{2} + x_{1} + x_{1}*x_{3},\\ ...
0
votes
1answer
200 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
344 views

How to find whether the line is inside the polygon or outside.

I have a polygon How can i prove whether the black color line lies outside the polygon or inside the polygon . Given the coordinates of the black line and all the vertices of the polygon.
1
vote
1answer
68 views

When is a convex polygon inscribable?

Defining the diameter of a convex polygon as the maximum possible distance between all pairs of vertices, can we conclude that the convex polygon is inscribable (i.e has all its sides as chords of a ...
1
vote
0answers
28 views

sweeping edges till they get a given elevation on an oblique plane

I am constructing wireframe model of 3d objects (prisms,..etc.). from a triangular mesh, I have obtained boundary points and fit striaght lines in order to get polygon edges refering to prism ...
0
votes
1answer
81 views

Packingof Spheres in 3D

I am looking to find out the size of the largest sphere , that can fit in the voids created by packing spheres ( hcp) of radius R.
0
votes
1answer
98 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
83 views

Correcting plane parameters with the fixed azimuth angles

I am trying to reconstruct specific 3d objects such as cubes, pyramids and so on. For this, i am using point cloud data and then fitting planar surfaces for the segmented point patches. Planes ...
0
votes
1answer
57 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: ...
1
vote
1answer
188 views

Ellipse arcs. Draw a tangent line in the end point or make arc longer?

I read this article: link It describes how to draw ellipse arcs at all from svg. Each ellipse is described with the following params (and I know them): x1, y1, x2, y2 - arc from point (x1, y1) to ...
5
votes
2answers
168 views

Finding the largest circle that contains a single point in a set (and no other point)

Given a bounded $A \times B$ rectangle with a set of chosen coordinates, generated for example with the command: ...
0
votes
0answers
25 views

Level set of 2D gaussians

I'm looking for a numerical method to rapidly find the level set $\{x,y\} | f(x,y)=h$, where $f(x,y)$ is a sum of a 2d gaussians (forming a mixture model), and $h$ a constant. Here's an example ...
1
vote
0answers
166 views

Formula for intersection of “power” curve and parabola.

EDIT I have edited this question to make it more clear. I have spent quite some time trying to find this on Google, but haven't succeeded. I need the formula(s) to determine the intersection ...
1
vote
0answers
27 views

Length of the voronoi diagram

Does there exist an algorithm for computing the length of the voronoi diagram of a set of points or just gives the intersection points of the voronoi diagram?
1
vote
0answers
57 views

largest polygon from segments

There is a set of segments. and I want to calculate the area of the largest polygon which can be build using these segments. I try to search it, but I can't find anything. thanks
1
vote
1answer
102 views

Graphics clipping: How can repeated half-space clipping fail?

Hi I am currently going through the past exam problems and I am stuck on this clipping problem. Could you give me some hint on how to solve it? If we clip a polygon to a window, it is inadequate ...
1
vote
1answer
59 views

Center of Distance

I am given $N$ points in a 2D plane($x$ and $y$ coordinates). I have to find a point in this plane with coordinates $X$ and $Y$ such that: $$\sum_{i=1}^N \max\{|X - A_i|, |Y - B_i|\}\text{ is ...
1
vote
2answers
128 views

Checking convexity from outside

Is there any method or algorithm to determine convex (or non-convexity) property of a region from outside (perimeter) ? One way is plotting tangent line in each point of perimeter and discuss how ...
1
vote
1answer
143 views

On finding the nondominated set of vectors. How to understand this algorithm?

L et us denote by $x_i(v)$ the $i$th coordinate of $v \in \mathbb{R}^d$. Then $v = \left [ x_1(v), x_2(v), \dots ,x_d(v) \right ]$ We say that a $v \in \mathbb{R}^d$ dominates another vector $w \in ...
7
votes
2answers
150 views

How to check if polylines can be untangled?

In a program I'm writing I need to be able to check whether a straight line between two points is homotopic to a polyline between them. For example in the below example the first one is equivalent to ...
0
votes
2answers
173 views

Proof of the following: How many $(n-2)$ dimensional faces from a corner of a hypercube

I asked a question earlier regarding the number of $(n-2)$ dimensional faces exiting a corner of an $n$ dimensional hypercube. (For example the number of points in a corner of a square, or the number ...
1
vote
0answers
82 views

Optimal bounding boxes selection for $N$ rectangles

Suppose that I have $n$ straight rectangles on a plane $r_i = (x_i,y_i,w_i,h_i)$. Each rectangle has a cost function, its area $A(r_i) = w_i \cdot h_i $. I can also "merge" 2 or more rectangles into ...
0
votes
0answers
34 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 ...
3
votes
1answer
82 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 ...
4
votes
1answer
87 views

Covering all the edges of a hypercube?

Consider an arbitrary $n$- dimensional hypercube: If we select $n - 1$ corners of that hypercube and highlight all $(n - 2)$ dimensional elements that originate from each of the corners is it ...
2
votes
1answer
68 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 ...
0
votes
1answer
952 views

How to find rotation angles along X,Y,Z axes with a known vector to bring the axes to correct situation

I am working with 3d point data. When I checked the data I realized that there is some error on my data and need to do some kind of rotational rectification because the points which should be ...
0
votes
0answers
144 views

how to get optimal vector, which is parallel to intersection line of many plane (Least Square way)

My idea is to construct the best optimal 3D line representing the intersection of many 3D planes. (As we know, due to fitting errors or data errors, the fitted planes might not intersect exactly ...
0
votes
1answer
206 views

my plane is not vertical, How to update 3D coordinate of point cloud to lie on a 3D vertical plane

I have a bunch of points lying on a vertical plane. In reality this plane should be exactly vertical. But, when I visualize the point cloud, there is a slight inclination (nearly 2 degrees) ...
4
votes
1answer
45 views

How can I geometrically (or geographically) group items together?

I'm a programmer, and I'm working on a project that takes a bunch of photos and separates them into groups by their gps coordinates. I have no experience in things like geometric group theory so I'm ...