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
32 views

Proof of correctness of a formula for the area of a polygon

Let $P$ be a $n$-gon with vertices $(x_1,y_1),\ldots,(x_n,y_n)$ enumerated clockwise. Then the area $\text{Area}(P)$ of $P$ is $$ \text{Area}(P) = \sum_{i=1}^n\frac{1}{2}(x_{i+1}-x_i)(y_{i+1}+y_i).$$ ...
2
votes
0answers
49 views

packing problem of semicircles into rectangle

I have problem. How can I get the maximum amount of semicircles (for example radius $35\;mm$) into rectangle $(485\times 185\:mm)$. I found many articles about packing of circles but nothing about ...
2
votes
0answers
49 views

Intersecting convex figures

Take in the real plane a finitely long horizontal line segment and connect the two endpoints by a convex path, above the segment, with the property that the only extreme points of the convex hull of ...
1
vote
1answer
47 views

Total number of lines in a 2D grid

I have a 2D grid of $M \times N$ points. I need to find the total number of lines (not line segments) passing through these points including the diagonals. For example: $M=2,N=2$: Number of lines $= ...
0
votes
0answers
17 views

Extension of Isovist concept for a point - to Isovist for a polygon

There is the concept of Isovist/Visibility polygon. They both talking about volume of space visible from a given point in space. My question: What is the algorithamic solution of this problem for a ...
1
vote
1answer
23 views

What is an offset bisector in 2D polygon skeletonization?

I'll be referring to the definition of the offset bisector from the definitions section of CGAL's 2D Straight Skeleton and Polygon Offsetting module. The halfplane to the bounded side of the line ...
0
votes
0answers
9 views

Integrate gaussian over general simplex

I need to compute the volume of an $n$-dimensional simplex where some dimensions are distributed uniformly and some normally. Can this be approximated well in polynomial time?
-1
votes
1answer
44 views

How can I find an algebraic formula to test whether two line segments intersect or not?

Suppose, $AB$ and $CD$ are two line segments. And, they have slopes $m_1$ and $m_2$ respectively. They will intersect with each other if, $m_1 \ne m_2 .$ Suppose, $A(x1, y1); B(x2, y2); C(x3, y3); ...
1
vote
1answer
37 views

How many techniques are there to test collinearity of $n$ points?

How many techniques are there to test coliniariry of n points? For example, suppose we have 4 points A, B , C, D. How many ways can it be tested that they are collinear? This answer lists 03 ...
1
vote
1answer
26 views

What is the name for the image form you get you take a line segment and sweep it through a region of space?

For instance, if you were to take a line segment and translate it along a coplanar path, then you'd get a plane. If the path is cyclic and on that path you rotate the line segment on the axis ...
1
vote
1answer
52 views

Determining the position of a polygon inside a circle from only the angle of opposing sides/edges.

For illustration click here I have a simple convex irregular polygon (octagon in example image) inside a circle (circle and polygon are not always concentric and never touching or intersecting) and I ...
0
votes
1answer
44 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 ...
3
votes
0answers
38 views

'Unrolling' the neighbourhood of a space curve

I have a space curve $\gamma : \mathbb{R} \longrightarrow \mathbb{R}^3$, sampled at $n$ discrete points. I have implemented an algorithm that gives me an approximation to $\gamma$'s tangent, normal ...
2
votes
1answer
61 views

sample variance of regular polygon upon superimposition of vertices

Given, the vertices of a regular polygon, the centroid here would be the sample mean of the vertices and we assume it to be at the origin. The distance from each vertex to centroid is ...
1
vote
0answers
17 views

Epipolar geometry - Fundamental matrix derivation (Hartley, Zisserman)

I have a question to the following derivation of the fundamental matrix by Hartley and Zisserman in "Multiple View Geometry in computer vision" (Link, page 5): Why is it possible to do the very ...
3
votes
2answers
63 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 ...
5
votes
0answers
48 views

Reconstruct polyhedron from sections

There is a convex polyhedron $P \subset \mathbb{R}^{3}$ and there are its planar sections $S_{1}, \ldots, S_{n}$ througth planes $\pi_{1}, \ldots, \pi_{n}$, $S_{i} \subset \pi_{i}$. All these $S_{i}$ ...
0
votes
1answer
34 views

equation of a cylinder jacket

how would you calculate this? A circular cylinder, height $14$, base radius $2$, has the axis of rotation! What is the equation of the cylinder jacket when the center of the base circle is the ...
6
votes
0answers
115 views

Balanced, center-free set. [closed]

We say that a finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC=BC$. We say ...
0
votes
3answers
40 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 ...
2
votes
0answers
21 views

Sum of distances of points in unit closed disk

Let $D$ be the closed unit disk in the plane, and let $p_1, p_2, \dots, p_n$ be fixed points in $D$. My question is, does there necessarily exist a point $p$ in $D$ such that the sum of the distances ...
0
votes
0answers
39 views

Relation between farthest pair of points and closest pair of points in plane

I am writing program for obtaining distance between shortest and farthest pair of points among the given points in plane .I am able to calculate them both the shortest one using divide and conquer ...
2
votes
0answers
54 views

3D kinematic geometry problem motivated by chemistry

It is well known that six carbon atoms can form a ring called cyclohexane. Since the angle between bonds is $\cos^{-1}\left(\frac{-1}{3}\right)\approx 109^\circ$, the ring is not a planar hexagon. ...
0
votes
1answer
36 views

Tetrahedron subdivision

What are all the possible subdivisions of the P3 tetrahedron (i.e. for each face, 3 vertices plus two points per edge, located at 1/3 and 2/3, and the centroïd of the face, so a total of 20 points for ...
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 ...
0
votes
0answers
8 views

Rotational normalisation of a sequence using PCA

I have a 1D contour, defined as a sequence of points in 2D space. For arguments sake, lets say I want to achieve rotational normalisation by aligning the direction of the first principal component of ...
0
votes
0answers
40 views

Unique Cicum-Sphere in n-Dimensions

I want to know if there is a generic way to find the circumcenter of an (n-1)-simplex in n-dimensions. Does there a exist a unique sphere which passes through n-points in n-dimensions? For example say ...
6
votes
2answers
95 views

How to determine whether a point is inside a closed region or not?

Take the following parametric equation of an implicit curve as an example: $$ \left\{\quad \begin{array}{rl} x=& 9 \sin 2 t+5 \sin 3 t \\ y=& 9 \cos 2 t-5 \cos 3 t \\ \end{array} \right. $$ ...
0
votes
0answers
36 views

Relation between parallel transport and Jacobi field II

Before I asked a question here: Relation between parallel vector field along a geodesic and Jacobi field along that same geodesic The current question is related, and actually arise from numerical ...
0
votes
1answer
27 views

finding volume of an n-dimensional pyramid numerically

In my experiment I need to compute hypervolume/area from a set of points, let's start with a base case -- Triangle: In this case, I have 3 points in a 2D space and they make a triangle, $p_1 = ...
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 ...
1
vote
2answers
106 views

Circumcenter of Tetrahedron (in 4D)

I am trying to calculate the circumcenter of a tetrahedron in 4 dimensional space. Basically what I am looking for is the center of the smallest sphere which passes through all 4 vertices of the ...
2
votes
0answers
42 views

Compute volume of the tetrahedron from circumsphere test

I'm working on a computational geometry algorithm. In every iteration I solve the matrix below, where (a,b,c,d) are the vertices of a tetrahedron, and e is an arbitrary point. Solving the determinant ...
6
votes
3answers
117 views

Way to measure the similarity/difference of 2D point clouds

i need a way to measure the similarity or difference of two point clouds? The number of points in each point cloud can be different. The Point clouds are already aligned. By similarity I mean the ...
0
votes
0answers
6 views

Equalize length of 1-ring edges of vertex

My question is how to equalize the length of edges in 1-ring neighbours of while-circled vertex in the below figure Hope to see your answer!
1
vote
0answers
81 views

Find the intersection between two convex hulls, in this specific case

We work over $\mathbb{R}^K$. Let $V$ the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$, . Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
1
vote
2answers
53 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
0answers
13 views

Prove Theorem with Groebner Basis

I'm trying to prove some theorems using Groebner Basis (as described in Cox, Little and O'Shea Link ) The mentioned book gives as an excercise to prove Pappus theorem using the given methodology, ...
0
votes
1answer
50 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
34 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
18 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
36 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
85 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
84 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
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 ...
0
votes
0answers
61 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
44 views

does any polyhedral partition admit a convex piecewise quadratic surface defined over?

Given a polyhedral partition, i learnt that there exist some conditions for the existence of a convex piecewise affine surface over this partition for example the following study. ...
0
votes
0answers
63 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
22 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?