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

0
votes
1answer
69 views

Generating Vectors under Constraints on 1 and 2 norm

Update: I left out some important information in my previous description... I am actually dealing with a special problem, which is better described as follows: Given user-specified parameters ...
2
votes
1answer
328 views

Distance between point and plane & orthogonal projection matrix

I am poor in mathematics and want to learn few fundamental ethics to understand some of advanced things; For plane $i$, denote $n_i\in\mathbb{R}^3$ and $o_i\in\mathbb{R}^3$ respectively as its normal ...
4
votes
1answer
147 views

Potential Division by zero in the construction of NURBS basis functions: how to handle?

Some background context In reading about NURBS I saw the definition that the B-Spline basis functions are defined by a recurrence relation. $N_{i,n} (u)= f_{i,n}(u) N_{i,n-1}(u) + g_{i+1,n}(u) ...
2
votes
1answer
486 views

Angle between different rays (3d line segments) and computing their angular relationships

I have several positions (say A,B,C,..) and I know their coordinates (3d). From each point, if a certain ray is passing in a way to converge them at a given (known) point (say O). This point O ...
1
vote
0answers
85 views

viewing ray geometry - with multiple aerial photographs

I am working with multiple aerial images. My idea is to model 3d objects (only upper parts). I am having known orientation parameters. As I am new to this field so that, I want to clarify few general ...
4
votes
1answer
160 views

Intersection of planes by forming 3d lines

If I have $n$ known planes (known normal vector and a point on a plane) that intersect each other in such a way so as to form closely located 3D lines, then (1). To get a common single 3D line to ...
3
votes
1answer
175 views

Partitioning a set of rectangles into disjoint subsets each of which consists of disjoint rectangles

Suppose we have a list $R$ of axis-aligned rectangles in the plane. There is the well-known problem of determining the maximum subset of $R$ which consists of disjoint rectangles; this problem is ...
2
votes
1answer
118 views

incident angles between rays, falling on an oblique plane

I am having really two simple questions, but following two things are confusing me. Question 1 If I know plane parameter (v3) of a given plane (say AB); if a pair of rays are incident at a ...
4
votes
0answers
125 views

Biggest ball included in an intersection of balls

I would like to prove that for any family of balls $\{B(c_i,r_i)\}_i \subset \mathbb{R}^d$ such that $\{c_1, \dots, c_n\} \subset \bigcap_i B(c_i,r_i) $ and $\forall i, r_i \geq 1$, there exists a ...
1
vote
1answer
52 views

What do we call the angular arcs between two edges of triangles?

I've been trying to find a geometry library for java which is as high level as describing angles between adjacent sides of triangles given 3 sides. So, what do we call such kind of arcs. In many ...
2
votes
2answers
109 views

Books for Geometry processing

Please suggest some basic books on geometry processing. I want to learn this subject for learning algorithms in 3d mesh generation and graphics. Please suggest me subjects or areas of mathematics i ...
2
votes
1answer
82 views

Computational geometry

Computational geometry? (Computational geometry) Given a set of n randomly scattered points for even n = 2,4,6,...,50 . Find the maximum number of lines between the pairs of nodes in such a way the ...
2
votes
1answer
425 views

Circle Packing: Unsolved Problem in Geometry?

Graham and Sloane minimize the second moment of the centres of a number discs in order to maximize their compactness. They use computational geometry techniques to find the optimal packings for ...
1
vote
2answers
514 views

Finding the tangents common to two rotated ellipses?

Is there a way to find the four tangents that two rotated ellipses share? I believe that if two ellipses do not intersect and do not contain one another, they will have four tangents in common and I ...
0
votes
1answer
655 views

closest pair in N-Dimensional

I have to find the closest pair in n-dimension, and I have problem in the combine steps. I use the divide and conquer.I first choose the median x, and split it into left and right part, and then find ...
1
vote
2answers
96 views

Approximating Euclidean geometry, restricted to $\mathbb{Q}$

I'm having trouble putting this into a fully coherent question, so I'll give the broad question, then a few bullet points to give you a better idea of what I'm asking. I'm looking for a line of ...
3
votes
1answer
85 views

Linear, Bi-linear or better

I have been writing some code to do some interpolation of 2D data on an irregular grid. So far what I have done is: Triangulate the known points using Delaunay. Find the vertices of the triangles ...
1
vote
1answer
114 views

Winding a space curve

Can I find parametric equations for a curve that is winding another curve, which I know -- let's say it's $\vec{f}(t) = (x(t), y(t), z(t)) = \{\sin (t)+2 \sin (2 t), \cos (t)-2 \cos (2 t), -\sin (3 ...
2
votes
1answer
38 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
174 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
107 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
201 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
45 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
112 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
68 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
75 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
129 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
93 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
85 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 ...
6
votes
2answers
97 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
292 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
63 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
55 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 ...
2
votes
2answers
657 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
47 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
86 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
437 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
65 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
146 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
646 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
254 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 ...
6
votes
4answers
741 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
160 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
134 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
183 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
41 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
69 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 ...
2
votes
1answer
100 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
50 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
68 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 ...