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
vote
2answers
60 views

Tetrahedra from it's inscribed sphere

I'm facing a geometrical problem: Given a sphere S, I want to calculate the vertices of the tetrahedra T whose inscribed sphere is S. In other words I want to calculate a tetrahedra from it's ...
0
votes
1answer
225 views

How do I calculate center of mass of a grid-type object?

I am making a game with 2D objects that are grid based. These objects are made out of tiles that are actually the cells of the grid. Each tile has a "mass" that is more than 0 and no upper limit. I ...
0
votes
1answer
41 views

Find all nearest points

I have two sets: $$P = \{p_1, p_2, ..., p_n\}$$ $$Q = \{q_1, q_2, ..., q_m\}$$ For each $p_i$ point I need to find all nearest points in $Q$. I.e., $$p_i \rightarrow \{ q_{i_1}, q_{i_2}, ..., ...
0
votes
1answer
28 views

Given a known line segment and two known horizontal lines, how do I find the line subsegment between the two parallels?

I am trying to clip a line segment between two parallel horizontal lines. I know the location of the two vertices on the larger segment, but need to know the points at which it intersects the ...
0
votes
0answers
39 views

What is the mathematics behind the two animations?

I found two animated GIFs from a designer's website, which looks very impressive: My questions are: what is the mathematics behind them? How to obtain the mathematical formulas and equations of ...
0
votes
1answer
31 views

What does R^d in last lines refer to

The image above is snapshot in the journal Geometric Approximation http://sarielhp.org/papers/04/survey/survey.pdf via Coresets .I could not figure out what is ...
0
votes
1answer
166 views

Knowing only the coordinates of the North-East and South-West corners of a rectangle, how to check if a point is inside a rectangle?

This is similar to this question. What's different is that only the coordinates of the North-East and South-West (or North-West and South-East) corners are known. My question is, can you directly ...
-2
votes
1answer
101 views

(x,y) coordinates from gluing together a sequence of right triangles with arbitrary angles [duplicate]

I have been scratching my head all day over this question for one of my assignments. I haven't made any progress and I'm at the point of giving up. Here's what I need help with. Start by gluing ...
2
votes
1answer
55 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 ...
0
votes
0answers
68 views

What is the shape of the set of integer sided acute triangles with largest side n?

I played around with Gauss circle problem and found that if you take a certain sum in reverse and "in forward" and subtract the resulting sequences you get the OEIS sequence: https://oeis.org/A247588 ...
0
votes
0answers
109 views

How to use CVX to solve this problem?

I have a function in the variables $x_{kl};\ k,l=1\ldots,m$, $$\sum_{i=1}^n \sum_{j=1,j<j'}^{N_i}\left( b_{ij} b_{ij'}- \sum_{k,l=1}^{m}x_{kl}f_k(a_{ij})f_l(a_{ij'})\right)^2$$ where ...
1
vote
0answers
26 views

Find largest regions bounded by a set of planes

Suppose we are given a set of planes that partition the unit cube into a large number of regions. Is there a computationally efficient way to find the region with the largest volume?
2
votes
0answers
106 views

Understanding BlowUp Computation in Singular

Many of us might know that "Singular" is a computer algebra system for Algebraic Geometry, Commutative Algebra and Non-commutative algebra. This is a procedure in "Singular" for computing blowups. ...
0
votes
0answers
40 views

Finding the vertices of a square giving the mid point and radius

I'm a programmer with terrible mathematics skills, but I'm getting by with studies. I'm trying to find out the vertices (x,y) of a square, giving the ...
1
vote
1answer
138 views

What is a composition of two binary relations geometrically?

the composition was defined as follow: (a,b) \in (R;S) <=> there is c | (a,c) \in R and (c,b) \in S . If our two relations R and S are two convex polygon ...
0
votes
2answers
133 views

How to compute Convex hull of set points from voronoi diagram

Assume $n$ points in the plane and their Voronoi diagram are given, prove that the convex hull of the points can be computed in linear time.
1
vote
1answer
151 views

Convex hull solving using a rubber band?

The convex hull can be found by stretching a rubber band so that it contains all the points and then releasing it. So my question is : lets assume that we have a robot (a theoretical robot) to solve ...
7
votes
0answers
83 views

Fast search of local positive quadruples on the sphere

Let $U = \{u_{1}, u_{2}, \ldots, u_{n}\} \subset \mathbb{R}^{3}$ be the finite set of points on the unit sphere in $\mathbb{R}^{3}$: $||u_{i}||_{2} = 1$ Definition: Quadruple of points $(u_{i}, ...
2
votes
2answers
308 views

Find polygon with smallest perimeter that encompasses all points

Given a random set of points in 2D space such as: How would one go about finding the smallest perimeter polygon that encompasses all points and has a point as each one of its vertices? For the ...
1
vote
1answer
40 views

Why simple polygons in plane have this property?

If we are given a simple polygon $P$ in the plane by the points $A_1, A_2, \dots, A_n$. How can we prove that there are $3$ consecutive points $A_i, A_{i+1}, A_{i+2}$ (if $i = n$, for $A_{i + 1}$ and ...
2
votes
0answers
33 views

Efficient algorithm for calculating hypervolume

Given a $d$-dimensional hyperrectangle that spans from the origin to the integer coordinates $l_1,l_2,l_3,\cdots,l_d$. If $V$ is the hypervolume of the solid formed by all points in the ...
0
votes
0answers
38 views

What does “maximum geometric error of a chunk” mean?

In this paper, on the top of page 7 it says, Where $\delta$ is the maximum geometric error of a chunk ... What does that mean? Thanks :D
0
votes
0answers
45 views

How to navigate around a smooth surface?

Suppose I want to find the shortest path between two points in $\Bbb{R}^3$ with smooth obstacles in the way? I understand things like Dijkstra's algorithm for shortest paths on a graph. But what about ...
3
votes
1answer
57 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
76 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 ...
13
votes
1answer
175 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
130 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 ...
1
vote
1answer
59 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
29 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
66 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
60 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
111 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
176 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
46 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
30 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).
4
votes
1answer
508 views

Points in general position

I'm really confused by the definition of general position at wikipedia. I understand that the set of points/vectors in $\mathbb R^d$ is in general position iff every $(d+1)$ points are not in any ...
0
votes
2answers
419 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
80 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
1k 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 ...
1
vote
1answer
99 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
80 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
90 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
58 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
156 views

Number of layers in nested convex hull

Find the maximum number of nested convex hull
0
votes
1answer
62 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 ...
2
votes
0answers
43 views

Geometric Median and Voronoi Diagrams

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
310 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
174 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
1answer
115 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
25 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} = ...