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

Fragemented linear feature alignment technique

I am having set of linear features lie on a plane (it does not a matter whether the pane is vertical or horizontal). all linear features are either parallel or othogonal to the vertical axis or ...
0
votes
1answer
141 views

Perpendicular to a vector at point on the vector

I am working with a model where I have to calculate a perpendicular to a vector through two points $\mathrm{P_1}$ and $\mathrm{P_2}$ (3d) at point $\mathrm{P_3}$ on the line joining these points. ...
1
vote
2answers
94 views

How to find co ordinates of a triangle after increasing the area by a factor of $\alpha$?

i am given with a triangle $\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\}$ and the area need to be increased by a factor $\alpha$. can i anyone let me know formula to find the co ordinates of new triangle? There ...
2
votes
1answer
155 views

Lloyd's algorithm in normed vector spaces

How do I run Lloyd's algorithm in a normed vector space? The space: L*a*b* color space, finite sRGB segment, $R^3$ The distance metric: CIE94 using L*C*h* information derived from the L*a*b* ...
2
votes
1answer
43 views

How to estimate orientation errors of an image with respect to known data (line features)

I think this is very simple but for me, it is confusing to figure out a way. Here is my problem. I have been given a 3d line segment list obtained from a field survey. So I know each end point ...
1
vote
1answer
87 views

angle between steepest gradient of two plane

IF I have two 3d planes such as Oab and Oa'b'. If these two planes intersect a horizontal plane and the intersection of each plane makes AB and A'B' lines. then, Does the angle between AB, A'B' ...
0
votes
1answer
61 views

$2$ planes and angle between them

IF I have two $3d$ planes such as Oab and Oa'b'. If these two planes intersect a horizontal plane and the intersection of each plane makes AB and A'B' lines. then, Does the angle between AB, ...
0
votes
1answer
69 views

obtainig a line 3D from multi view geometry

If I have been given multiple view images having known orientation parameters, then from a selected image line segment (corresponding line segments from each image) how could I compute a line 3D in ...
0
votes
1answer
104 views

Steepest slope gradient of a vertical plane

I know the steepest slope gradient (Azimuth) of a 3D plane can be obtained by projecting normal vector onto XY Plane. So, when the plane is slant, the steepest gradient will be a some value. ...
1
vote
1answer
72 views

Predicting the size of epsilon-net in SU(2)

I'm writing an algorithm that takes as input a finite set of matrices in SU(2) and consequently tries to generate an '$\epsilon$-net' by computing all possible matrix products (up to a given depth). ...
2
votes
0answers
65 views

Calculation of the fundamental group from triangulations

Is there - say, for a triangulable surface - a concrete algorithm how to calculate the fundamental group of the surface from a given triangulation, seen as a graph (of its 1-skeleton), given as an ...
5
votes
2answers
85 views

Find the most vertical line in a point set in $O(n \log n)$ time

Input: a set of $n$ points in general position in $\mathbb{R}^2$. Output: the pair of points whose slope has the largest magnitude. Time constraint: $O(n \log n)$ or better. Please don't spoil the ...
2
votes
1answer
237 views

Obtaining Least square adjusted single line by intersecting many 3D planes

I am working with many 3D planes and looking for a Least square solution for below case. IF I am having many number of 3D planes knowing only one point and the normal vector (for eg. O1 and N1), ...
0
votes
0answers
56 views

transformation function using genetic programming

If I have a set of points in two spaces, say set $A$ contains 50 points and set $B$ contains 50 points. I have to find a transformation function such that if I transform the points in set $A$ using ...
1
vote
0answers
52 views

How to estimate error pattern of a set of line segments with respect to given reference segments (2D case)

I am having set of pair of line segments (2D). Though each pair should be coincided on top of each other they are not so. I have been the reference data and then I extracted other line segments ...
1
vote
2answers
279 views

Determing the distance from a line segment to a point in 3-space

Imagine I have a line segment defined by endpoints $p_1$ and $p_2$, and some 3-space coordinate $q$. Is there a robust (in the sense of never giving divide-by-zero errors) way to quickly determine ...
3
votes
0answers
45 views

For which coverings by “geometrically nice” sets does the nerve admit “Vietoris-Rips-like” approximations?

It is well known that the nerve (or Čech complex) of a covering by metric balls is nicely approximated by the Vietoris-Rips complex. Being a flag complex on its 1-simplices, the latter is ...
1
vote
3answers
75 views

Are there any Heron-like formulas for convex polygons?

Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
0
votes
1answer
319 views

The equation for the circle defined by two intersecting spheres in 3-space?

We define two spheres, $S_1$ and $S_2$, of radius $r_1$ and $r_2$, centered at 3-space points $p_1$ and $p_2$, respectively. What equation gives the circle in 3-space at the intersection between the ...
1
vote
2answers
62 views

What is the equation stands for in geometry(intuitively)?

I am writing a bilinear interpolation method. This method can be abstract by solve the equation A*x = b, A is a 4x4 matrix below: $A=\begin{pmatrix} 1 &x_1 &y_1 &x_1y_1\\ 1 ...
1
vote
1answer
114 views

Algorithm Design for Delaunay Triangulation?

I am very much happy after seeing some very good answers in this site. I am trying to design a algorithm for the construction of Delaunay Triangulation using Randomized Incremental Algorithm.(I wont ...
3
votes
0answers
591 views

Turning radius of a vehicle

What's the minimum turning radius of a vehicle, rectangular in shape, with length l units and width w units? One key point to consider, would be that, the inclination of the front wheels can be ...
-1
votes
1answer
207 views

How to change XYZ axes system into another 'xy' system

I have $3D$ point set lying on a vertical plane. This plane is not parallel to either $X$ or $Y$ axis but makes an angle (say, $\theta$) to $X$ axis. And also it has some ($+$ or $-$) intercept to the ...
5
votes
4answers
628 views

How to know location of a point?

I have a circle formed with three given points. How can i know whether another given point is inside the circle formed by previous three points. Is it determinant i need to calculate? Then what are ...
0
votes
1answer
127 views

Notation and meaning of coordinate system in geometry

I am trying to understand projective geometry to build a 3d scanner, using this text. http://mesh.brown.edu/byo3d/notes/byo3D.pdf When describing an idea pinhole camera it says In the ideal ...
3
votes
0answers
105 views

How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?

I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...
0
votes
1answer
138 views

Does a generalized intersection test exist? If yes, how does it work?

I'm looking for an algorithm to test if an N-dimensional object (defined by the convex hull of N+1 vertices) and an M-dimensional object (defined by the convex hull of M+1 vertices) intersect within ...
1
vote
0answers
39 views

problem in dimensionality reduction

I am using multidimensional scaling to plot my data in R. However there is a hierarchy in my dataset which i want to exploit and I am using the delaunay triangulation to visualize the plot. So now I ...
1
vote
1answer
62 views

$2d$ line equations in polar coordinates

I know in polar coordinates, a $2d$ line equation is given in the form of $$r = x \cdot \cos(\theta) + y \cdot \sin(\theta),$$ where the parameters are defined as in this. I want to derive an ...
1
vote
1answer
91 views

What is the mathematical relationship between the number of faces in a mesh and its vertices?

An "open and planar quad mesh" (more description below) with 4 mesh faces has 9 vertices, the same mesh with 8 faces has 15 vertices (2 faces at every X-axis row, 4 faces at every Y-axis ...
0
votes
1answer
45 views

a line perpendicular to a given line

I am confused now, I have a 2D line. If its equation is $r = x\cos(\theta) + y\sin(\theta)$, then what will be the line which is perpendicular to that line? Where $r, \theta$ is described ...
2
votes
0answers
58 views

Finding the smallest nonzero vector perpendicular to $\vec v$ with integer coordinates

Let $\vec v\in\mathbb Q^n$. Is there an efficient algorithm to compute the smallest (in the $\ell_\infty$ norm) nonzero vector $\vec w\in\mathbb Z^n$ such that $\vec v\cdot \vec w=0$? Equivalently, if ...
-1
votes
1answer
73 views

Limiting search space for efficient line matching [closed]

I have 2D line segments extracted from an image. So i know end point coordinates of them. also, i have some reference 2d line segments. Both line segments are now in vector form. comparing to ...
-1
votes
1answer
156 views

Buddhabrot Sewing machine [closed]

The Buddhabrot fractal traces the orbits of the points outside the Mandelbrot set. What design considerations need to be taken into account to create a computerised sewing machine that traces out ...
0
votes
1answer
414 views

Solving vector equations with dot products

I'm working on a triangle-triangle intersection algorithm using this article ("The Line Intersection of Two Planes" part). The problem is that I don't know how to solve vector equations with dot ...
2
votes
0answers
292 views

Algorithm for Collection of Shortest Paths in a Grid without any clash at a point of time.

The efficient algorithm needs to be done and proved for the best solution for the given problem: User inputs: (#) Size of the NxN Grid. (N); (#) No. of Paths: Z; (#) Source and Destination ...
1
vote
1answer
441 views

How to find the intersection of the area of multiple triangles

I have a couple of questions regarding finding the intersection of triangles. I have a system of 16 projectors that all have slightly different color gamuts. The color gamuts are represented by a ...
0
votes
1answer
106 views

Algorithm for computing the plane that passes through three arbitrary points

I'm writing a computer graphics library, and I'd like to compute the plane that passes through three arbitrary points, $p$, $q$ and $r$. I'm defining the plane in the form of $Ax + By + Cz + D = 0$. ...
0
votes
1answer
290 views

Radius of circle coverage of n circles in square packing configuration

Is there a reference about determining the minimum radius of a circle that would cover n circles of radius 1 that are in a square packing configuration ( see Wolfram's MathWorld packing packing ...
3
votes
1answer
116 views

Shortest triangulation is in general not a Delaunay triangulation

Let $P$ be a set of points. The minimal triangulation of $P$ is a triangulation $T$ of the points in $P$ such that the total length of the edges in $T$ is the smallest possible amongst all possible ...
3
votes
1answer
659 views

Star-Shaped polygons

We call a polygon star-shaped if there exists at least one point for which the entire polygon is "visible" from that point. The set of such points we call the kernel of the polygon. The art-gallery ...
0
votes
1answer
110 views

How to move a one 3D line from three 3d parallel lines

I have 3 parallel line segments (say AB, CD, and EF are line segments and they are nearly horizontal) lay on 2 slanted planes which have been intersected through the CD. If I projected all the line ...
0
votes
1answer
214 views

making three parallel lines (3d) with equal distance seperation

I have three parallel lines (3d lines). say AB, CD, EF. The center line i.e. CD is given by intersecting the two planes by which the AB, DE lie on. The shortest distance between AB and CD (say d1) is ...
1
vote
1answer
80 views

Diagonal of a convex polygon such that the obtained cuts have simmilar areas

Let $P$ be a convex polygon represented with a list of vertices specified by some orientation. Consider the following problem Problem. Find in linear time a diagonal of $P$ such that the absolute ...
4
votes
0answers
115 views

How many points does one need for an epsilon-net

Does anyone know, how many points does one need to have an $\varepsilon$-net on a unit sphere sitting in the three-dimensional Euclidean space? Thanks!
1
vote
0answers
56 views

Integration through a Rotated Square

I have a 2D square S. S is described by s, the side length, theta, the angle it is rotated by, and c, the position of S's center. There is an axis-aligned rectangle R that extends infinitely in the ...
5
votes
2answers
105 views

Voronoi Diagrams Proof

I am having a real problem with this proof about voronoi diagrams: Prove that $V(p_i)$ (i.e., the cell of $\operatorname{Vor}(P)$ which corresponds to $p_i$) is unbounded if and only if $p_i$ is on ...
2
votes
2answers
915 views

Proof that the Convex Hull of a finite set S is equal to all convex combinations of S

In $C^n$, how would you prove that the convex hull of a finite set $S$(convex hull being the intersection of all convex sets which contain $S$) is equal to the set consisting of all convex ...
1
vote
0answers
119 views

Approximating Bezier curves

I would like to approximate one cubic Bezier curve with two quadratic ones. In other words, I would like to split a cubic curve at some parameter t and approximate ...
3
votes
1answer
364 views

Ellipse center with three points and the semi-axis lengths given

Having three given points in the two-dimensional plane and semi-axis lengths $a$ and $b$ of an ellipse, how to determine the center? By construction (the "Euclidean way") or analytic geometry.