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
1answer
34 views

Graphing algorithm

I am not sure if this belongs on Mathematics Stack Exchange, but it is somewhat relavant here. The Problem If you've installed any graphing/plotting apps on your smartphone, you will notice that the ...
1
vote
0answers
4 views

Alternative to triple precision in line intersection computations

I often have to compute intersections of line segments using integer coordinates. The exact analytical expression involves the ratio of a third degree expression over a second degree one, and that ...
0
votes
0answers
14 views

Ways of partitioning n points into some cubes

Assume there're $n$ fixed points in $\mathbb{R}^d$ contained in a ball with radius $M$,and you can partition the space by cubic grid with cube's edge length $h>\epsilon$. How many different ways of ...
1
vote
0answers
19 views

population of dots with normal distribution of pitch

I want to generate a plot that shows a rectangle populated with dots, where the dot-to-dot distance (pitch) distribution is a lognormal (or a gaussian). I want to be able to change the mean dot-to-dot ...
0
votes
0answers
21 views

Getting Linear sum from sum of squares

I have sample space Ri = (44.19, 35.14, 57.23, 74.27, 47.27, 32.06, 21.75, 66.49, 25.01, 30.10, 77.53, 61.40, 74.45, 21.93, 20.84, 73.36, 82.62, 52.36, 40.23, 31.88, 1966.79, 2112.71, 1836.88), n = 23 ...
12
votes
1answer
151 views

Automorphism group of a lattice's Voronoi cell

Let $\Lambda$ denote a lattice of $\mathbb{R}^n$, i.e. $$\Lambda = \left\{\sum_{k=1}^n n_i\mathbf{a}_i\ \bigg|\ n_i\in\mathbb{Z}\right\},$$ for $n$ linearly independent vectors $\{\mathbf{a}_i\}$ in ...
0
votes
1answer
18 views

How to determine if some line segments are collinear

Let's say I have several Line Segments that are connected to each other and make a Polyline. How can I determine if they are ...
0
votes
1answer
21 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$? ...
1
vote
0answers
16 views

Finding other two vertices when one vertex and each point on the triangle is known ?

I am working on some gesture recognition for my game. I am stuck on a problem. I have one vertex i.e the starting point and every point on the triangle, I also have the centroid. So how do I find the ...
0
votes
1answer
17 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
32 views

Hypersphere - Pattern matching using Centroid, Radius and Diameter

I have a hyper-sphere formed with set of $n$-dimensional data points. I could calculate centroid ($X_0$), radius($R$) and diameter($D$). Using these $X_0, R, D$, how I can find whether the a given ...
0
votes
1answer
22 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
2answers
31 views

Scan line algorithm for intersecting polygons

Given two sets of polygons $P_1 = \{s_1,...,s_m\}$ and $P_2=\{s_m+1,...,s_n\}$ with total number of $n$ segments, the previous and next segment on it's polygon can be determined in $O(1)$. Describe a ...
1
vote
0answers
19 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
0
votes
1answer
16 views

Equality of polyhedra

Is a minimal representation for a polyhedron unique? And if so can we use this to prove that two polyhedra are equal (or maybe the same is a better definition).
0
votes
0answers
12 views

point-tuple orientation

Does something like point-tuple orientation exist? I read this book, pg 336, paragraph "One can even..." and I've bumped into this quite unfamiliar notation. Thanks for clarification. P.S. if someone ...
2
votes
1answer
25 views

points in general position

I'm really confused by definition of general position at wikipedia. I understand that the set of points/vectors in R^d is in general position iff every (d+1) points are not in any possible hyperplane ...
0
votes
2answers
70 views

Hexagonal Tessellation on a sphere

I want to detect collision of a sphere with another object and to find out(show) the deformation of the sphere. I have come to know that hexagon(regular)tessellation of a sphere is the most ...
1
vote
0answers
30 views

Find 3D concave hull based on original model and convex hull

I want to find the concave hull of a 3d model, with a threshold for the maximum edge size. Googling around let me to the following approach (mainly abstracting from 2d approaches): Determine the ...
0
votes
3answers
45 views

determine unit outward normal vector on a curve

It is necessary for me to find unit outward normal vector for the curve: $$\gamma=(x(t),y(t))$$ where $$x(t)=(0.6)\cos(t)-(0.3)\cos(3t)$$ and $$y(t)=(0.7)\sin(t)+(0.07)\sin(7t)+(0.1)\sin(3t)$$ I ...
0
votes
0answers
50 views

quadratic constraints representations

I have two surfaces of parameter $x \in \mathcal{X} \subset \mathbb{R}^n$ with $\mathcal{X}$ to be a polytope: $u(x) = ax + b \subset \mathbb{R}^m, z(x) = x^TAx + B^Tx + C \in \mathbb{R}$. If $m=1$, ...
0
votes
1answer
37 views

Convex hull of a set of points

Let $a_1,a_2...a_r \in R^n$ be points in $R^n$. Prove:$$CH(\{a_1,...,a_r\})=\left\{\sum_{i=1}^r\alpha_ia_i|\sum_{i=1}^r\alpha_i=1,\alpha_i\ge0\right\}=:K$$i.e. the convex hull of the $a_i$ is the set ...
2
votes
0answers
64 views

Similarity of Polyhedra: What is the measure?

When comparing two convex polyhedra, how can one determine if they are geometrically similar. Is there any algorithm to determine if one is the distorted or truncated version of the other? Vertex, ...
0
votes
1answer
30 views

Convex hull is convex

A set $C \in R^n$ is called convex if the line segment $L = \{ tp + (1-t)p | 0 \lt t \lt 1 \}$ between two arbitrary points $p,p' \in C$ is contained in $C$. The convex hull $CH(C)$ of a set $C ...
0
votes
0answers
29 views

Two convex polygon intersection from set of m convex polygons with total n vertices

I have a set of m convex polygons $(p_1,p_2, \ldots p_m)$. $n_i$ is the number of vertices in $p_i$. $\sum_{i=1}^{m} n_i = n$. Each polygon has vertices listed in anti-clockwise direction, starting ...
2
votes
3answers
27 views

Number of layers in nested convex hull

Find the maximum number of nested convex hull
0
votes
1answer
26 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 ...
1
vote
0answers
28 views

Geometric Median

Is there a relationship between Voronoi Diagrams and the geometric median? I know that it is impossible to find a closed expression for the geometric median, but the two concepts seem related.
0
votes
1answer
69 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. ...
-1
votes
1answer
52 views

Find the length of each side of a square containing regular hexagons [duplicate]

I have to find the length of each side of a square such that all the regular hexagons of same length side and radius lying inside the square have centers either inside the square or on the boundaries ...
0
votes
0answers
54 views

Mathematical proof to find the length of each side of a square filled with Regular Hexagons

I have to prove or disprove that in a square box if there are full regular hexagons( whose distance from center to every corner is r) inside it, then the centers of those hexagons should lie inside ...
0
votes
1answer
25 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
14 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
2answers
76 views

Sorting a list of points in 2-D clockwise

I have number of points with co-ordinate (latitude, longitude) in 2-D: Here is a collection of some points: \begin{array}{ccc} \hline No.& lon & lat \\ \hline 1& 84.07921& 24.49703 ...
0
votes
0answers
15 views

Proof of spherical Helly's theorem

I need to prove that if every three members of a system of convex sets on the surface of a sphere intersect, every member fits in some hemisphere and no four members cover the whole sphere, then the ...
1
vote
0answers
12 views

ellipsoid and paraboloid relation

My task was to programme a paraboloid and an ellipsoid. I implemented paraboloid as a set of points that's distance from the focal point and the distance from the plane is the same. After running the ...
0
votes
1answer
51 views

Is k-means clustering guaranteed to converge if using Manhattan distance?

The k-means algorithm is an iterative clustering algorithm that partitions the data points into K clusters (with centroids {$\mu_1, ... , \mu_k$}, minimizing the Sum-of-Squared-Error: $$ SSE = ...
0
votes
0answers
22 views

Maximal area intersection of half-planes in $\mathbb{R}^2$

Suppose we have $m$ half-planes $H_1,...,H_m$ in $\mathbb{R}^2$ such that $H_1 \cap \dots \cap H_m = \emptyset$. Let $A$ be a set of subsets $S$ of $\{H_1,...,H_m\}$ with non empty intersection and ...
0
votes
1answer
56 views

intersection of an ellipsoid and cylindrical plane.

I need to understand if an ellipsoid and a cylindrical arc intersect, what will be the general equation of the cutted ellipse? How can I solve for that equation? I know in 3D, the equation of an ...
1
vote
0answers
52 views

Algorithm to compute wether 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$ ...
1
vote
0answers
52 views

How to Compute the Torsion and Curvature of a Parametric Curve

So I have a parametric curve $\bf{r}=${$x(n),y(n),z(n)$} such that the functions $x(n)$, $y(n)$ and $z(n)$ are polynomials of $4$-th degree. I have several of these curves, and I want to calculate the ...
1
vote
2answers
47 views

Estimating the missing points of a 3D point cloud

Consider a cloud of N points (forming a smooth 3D object), in which n points are missing. Also, consider that there is no prior knowledge about the original shape of the point cloud. The only ...
2
votes
1answer
77 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 ...
1
vote
0answers
72 views

Minkowski sum of two polytopes via the halfspace representation

If i have two polytopes denoted by $P_1, P_2 \subset \mathbb{R}^d$, suppose their halfspace representations are respectively $H_1x \leq K_1$ and $H_2x \leq K_2$. Now, considering their Minkowski sum, ...
0
votes
0answers
32 views

Find points that defines the intersection of an ellipse with a plane.

I want to test for the intersection of two ellipses $E_1$ and $E_2$ in $\mathbb{R}^3$ represented on a computer. In some sense, this isn't a hard problem: ...
0
votes
0answers
85 views

Algorithm to optimize rectangles filling by rectangles

I have a set of rectangles, all of the same size (W,H) (in fact paper sheets). I have another set of n rectangles of different sizes (Wi,Hi), i = 1..n such that Wi <= W and Hi <= H (in fact ...
0
votes
1answer
101 views

How to calculate volume and surface area of three dimensional figures given set of three dimensional coordinates?

I have set of three dimensional coordinates, and the shape is unknown. I would like to calculate the surface area and volume for these coordinates approximately. What is the right approach to solve ...
0
votes
1answer
23 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 ...
1
vote
2answers
64 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 ...
0
votes
0answers
45 views

Can a polygon with minimal perimeter self-intersect?

Recipe. Do the following. Throw $N$ random points $(x_0,y_0),(x_1,y_1),x_2,y_2),\cdots,(x_{N-1},y_{N-1})$ in the plane.Define $(x_N,y_N)=(x_0,y_0)$ : enumeration is $\mod N$ . These points are joined ...