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

point inclusion in a half-plane 3D

I have a 3D half-plane defined using a line segment an a point (as shown in picture taken from here). I am wondering how I can detect if a point belongs to the half-plane. Is there any way to ...
1
vote
0answers
18 views

Is this projection optimization problem NP-hard?

Suppose we are working in ${\mathbb R}^d$ (dimension is not fixed), and we have a set of $n$ points $X = \{x_1,\ldots,x_n\}$ in that space. Given a query point $y$ inside the convex hull of $X$, we ...
3
votes
3answers
178 views

Check if a point is inside a rectangular shaped area (3D)?

I am having a hard time figuring out if a 3D point lies in a cuboid (like the one in the picture below). I found a lot of examples to check if a point lies inside a rectangle in a 2D space for example ...
0
votes
0answers
52 views

Determining N d-points yielding equal sums of Euclidean distances from M s-points

Given M source points (s-points), determine N, the number of destination points (d-points), and their locations (coordinates), such that the sum of the N Euclidean distances from each source point to ...
0
votes
0answers
35 views

Determing the Two Closest Vertices a Point Lies Between on Circumcircle

For a computational geometry application, I need to determine the two closest vertices that a point lies between on a circle that has been sliced into angular intervals. To illustrate the problem, ...
0
votes
3answers
66 views

How to traverse circle coordinates?

The problem I have is: Fill a circle by drawing one-pixel-wide horizontal lines across its inside area. My initial thought is to generate the circles' coordinates symmetrically to a vertical ...
1
vote
2answers
31 views

Maximal-Orthogonal Convex Hull (or Maximal-Rectilinear Convex Hull)

In my research, I have come across a this paper from the Computational Geometry field and I am not able to understand the concept of Maximal-Rectilinear Convex Hull of a given point set in plane. In ...
3
votes
1answer
177 views

Given 3 random points, what is the probability of these two situations involving a perpendicular bisector and distances?

Suppose we're given 3 random points $p_0=(x_0,y_0),p_1=(x_1,y_1),p_2=(x_2,y_2)$ from a two-dimensional continuous uniform distribution $\{U(a,b)\}^2$, for some $(a\in\mathbb{R})\lt (b\in\mathbb{R})$, ...
0
votes
1answer
30 views

Normal to a set of integer vectors

Given a set of $i$ integer vectors resting in $d$ space (with $i$ < $d$), how do you find a normal to the set of vectors while keeping all of the computations in $\mathbb{Z}$?
0
votes
0answers
80 views

how to compute horizontal angle of a pixel from a computer vision camera

My program needs to compute the angle of a pixel from a computer vision camera that has 120 degrees horizontal field of view, and resolution of 640 pixels wide and 480 pixels high. Program receives ...
0
votes
0answers
20 views

Finding the initial facet in giftwrapping

I'm struggling to understand how to find an initial facet via the giftwrapping algorithm. I understand that you start by taking a vertical hyperplane $H_1$, and seeing what point(s) it hits first on ...
0
votes
1answer
252 views

Rotations of a cube

I am trying to create a program using Python 3 which must simulate the rotations of a cube. However, I am struggling to figure out how to rotate that cube. I have the following formulas: ...
3
votes
3answers
119 views

Shortest path in a maze

There is a maze, which is nothing but made of $2$ parallel polylines, which looks like a zig-zag road. We have to find the shortest path between the entrance and exit. Any ideas on how to proceed? ...
3
votes
1answer
148 views

Maximum Side of a Square Dissected into Rectangles

Suppose a $m \times m$ square can be dissected into $7$ rectangles such that no two rectangles have a common interior point and the side lengths of the rectangles form the set ...
2
votes
1answer
72 views

segment intersecting a tetrahedron

I am trying to write C++ code to find the intersection points of a segment intersecting a tetrahedron. I reduced the problem like this: For each face of the tetrahedron (a triangle), find the ...
2
votes
2answers
42 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
71 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
74 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
92 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
29 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
77 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
15 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
49 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
46 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
28 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
87 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 ...
1
vote
1answer
56 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
43 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
65 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
47 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 ...
4
votes
2answers
118 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
54 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
45 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
152 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
333 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
26 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
112 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
57 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
51 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
28 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
15 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 ...
7
votes
2answers
144 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
61 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 ...
1
vote
2answers
133 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
22 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
292 views

Circumcenter of Tetrahedron (in 4D)

I am trying to calculate the circumcenter of a tetrahedron in 4 dimensional space. I was hoping for some concrete mathematical formula which can make this calculation more accurate.
2
votes
0answers
76 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
407 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 ...
1
vote
0answers
108 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
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 ...