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
votes
1answer
41 views

How to get the third point coordinates in isosceles triangle?

Isosceles triangle $ABC$ $AB = AC = d_1$ $BC = d_2$ $A = (x_1, y_1)$ $B = (x_2, y_2)$ $C = (x_3, y_3)$ $\angle BAC = \phi$ $\angle ABC =\angle ACB = \theta$ I want an equation for $x_3$ and $y_3$ ...
0
votes
0answers
29 views

A continuous centerpoint of a convex spherical polygon

In discrete geometry, a centerpoint $c$ of a discrete set $S$ of $n$ points in the plane is such that any half plane containing $c$ contains (roughly) $n/3$ points of $S$. (Such a centerpoint always ...
1
vote
0answers
11 views

Finding triangulations on 2D space by projecting lower hull of 3D

So we know that we can get the Delauney triangulation of a polygon if we map all points to the 3D space such that $p'=(p.x,p.y,p.x^2+p.y^2)$, compute the lower hull of that polyhedron, and then ...
3
votes
0answers
44 views

Understanding Newton polygons

I'm trying to understand the concept of the Newton polygon in relation to factoring polynomials over a field. I understand given a polynomial $$ 1+a_1x + a_2x^2+\cdots+ a_nx^n$$ that the Newton ...
0
votes
1answer
20 views

At what extent I can use trigonometric functions and properties with parametric curves?

I have a know-how and a library about trigonometry and trigonometric operations, I would like to know if I can possibly rely on trigonometry for parametric curves too and how the trigonometry from the ...
0
votes
1answer
15 views

What is and what are the use for an “ AINV preconditioner ” or “ SAINV ”?

In an article that I'm reading there is a mention to this "thing" and I absolutely don't know anything about it, for me it could be anything. I noticed that this thing is somehow related to the math ...
0
votes
0answers
48 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
0
votes
0answers
16 views

Data structure issues with incremental Delaunay triangulation

I am implementing the incremental algorithm of Delaunay triangulation with a data structure based on Faces (triangles): 3 vertex indices and 3 Neighbor indices. The issue I have is that the structure ...
1
vote
0answers
77 views

How can I define a measure of similarity between two line segments in $\mathbb{R}^2$?

I have two segments in $\mathbb{R}^2$ and I would like to define a measure of similarity between the two segments. My idea is that I can apply: a scale transformation $s$ in order to equate the ...
0
votes
2answers
36 views

Where is the interior of the polygon?

There is an axis-parallel simply-connected polygon given as a list of corners. How can I know whether a certain vertical segment has the interior of the polygon on its east or on its west? For ...
3
votes
1answer
56 views

filling an occluded plane with the smallest number of rectangles

I've got a specific problem which I'll try to describe as clearly as possible. I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular ...
6
votes
1answer
68 views

Putting fence around sheep

Convex hull algorithms are well known. However, in my case, the goal is slightly modified: Given $N$ points in a plane, construct convex polygon with minimal area so that it contains all points, and ...
0
votes
1answer
38 views

Formula of signed distance from hyperplane to point

Let $H$ be a hyperplane defined by the points $p_1, p_2, ..., p_n$ and single point $x$ generally out of the hyperplane. Is there any formula to calculate the signed distance between $x$ and $H$? I ...
1
vote
0answers
19 views

Traveling Salesperson tour monotonicity

Prove that the travelling salesperson tour TSP of a set S of points is monotone, that is, if S ⊆ S′, then the length of TSP(S) is less than or equal to the length of TSP(S′).
0
votes
1answer
40 views

Avoiding gimbal lock

I am not really sure if I understand the phenomenon of gimbal lock correctly. Say I have a vector $\begin{pmatrix} x\\ y\\ z \end{pmatrix}$. And I want to keep the vector's length fixed but move it ...
1
vote
2answers
34 views

Determining points on a circle in a particular plane

This is more of a computer graphics question really, but I was just wondering the efficient way to determine n equally spaced points on a circle, given a normal vector to the circle and the radius of ...
0
votes
1answer
14 views

Applications of logarithmic functions in shapes and geometries

As I understand this logarithmic functions are a family of functions where the equation for $f(x)$ is written like so $$\begin{align} f(x) = & \log_{a} x \\ & \mathtt{where\ }a\mathtt{\ is\ ...
2
votes
2answers
52 views

Given four points, verify if they form a Tetrahedron

As per the title, I've been requested to build a program that -given 4 points in space- determine if they form a 3D shape and if this is case to present it's volume. For the volume part of the ...
8
votes
2answers
193 views

Visual illustrations of circle packing theorem?

Circle packing theorem states: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G. Paper Collins, Stephenson: A circle ...
2
votes
1answer
50 views

What does $E^d$ mean?

I was reading the paper "Cutting Hyperplanes for Divide-and-Conquer" by B. Chazelle and in the introduction I came across the following: "Let $H$ be a set of $n$ hyperplanes in $E^d$." What does $E^d$ ...
2
votes
2answers
112 views

What is inside and outside of complex polygon?

I am reading this paper http://arxiv.org/pdf/1207.3502.pdf Given a complex polygon. Its edges may intersect. The algorithm finds out if given point is inside of polygon or not. It draws a line from ...
0
votes
2answers
45 views

Why are rectangular cartograms hard to generate?

I was reading this paper on rectangular cartograms - ...
1
vote
1answer
51 views

Prove that volume of a ball in a polytope is very small

An exercise in a book asks to prove that for a bounded convex polytope $P\subseteq\mathbb{R}^n$ defined as an intersection of $k$ closed halfspaces and for a unit ball $B^n$ contained in $P$ the ...
0
votes
0answers
21 views

Schwarz–Christoffel-like mapping on differentiable simple cubic spline boundary

For a concept of a computer game I have in mind I came to need that. I have a 2D pond, which has a boundary that is a simple differentiable cubic spline. There are ducks floating around, looking at ...
0
votes
1answer
31 views

Altitudes of Triangle

I have a triangle defined as 3 lines, each defined by two coordinate points A and B. I have the area of the triangle but need to calculate the 3 altitudes and their respective sides A and B points. ...
2
votes
1answer
68 views

how many unit balls are needed to cover a unit sphere (1-dense set on a unit sphere)

There is an exercise in a geometry textbook to prove that "any $1$-dense set in the unit sphere $S^{n-1}$ has at least $\frac{1}{2}e^{n/8}$ points". It is supposed to be easy. A set $T$ is ...
1
vote
1answer
74 views

Equation of hyperplane in Matlab

Given $n$ points in $n$-dimensions, using MatLab, how should we find the equation of the $(n-1)$-dimensional hyperplane passing through these $n$ points.
2
votes
1answer
34 views

Collinear points in 3dimension

Given three $3D$ points: $A,B$ and $C$, what is the procedure to check if they are collinear? In general, given $n$ points in $m$-dimension, how should one find out, if these $n$-points defines a ...
2
votes
0answers
56 views

How do I most efficiently find the perpendicular distance from a point to the convex hull of a collection of circles?

I have a collection of one or more line segments for which I know the (x,y) coordinates of the endpoints. The segments may or may not be parallel and may or may not intersect. Each segment endpoint ...
0
votes
1answer
30 views

How to test for a polygon witn n vertices if it's nonintersecting polygon or not?

How can you design an algorithm to know if an n-vertex polygon nonintersecting ? On what criteria is the test going to be
11
votes
3answers
157 views

is there an efficient algorithm for comparing collections of points?

Let's say you have two sets of M points $p_1...p_M$, and $q_1...q_M$, which reside in $\mathbb{R}^N$. Is there an efficient (e.g. polynomial in M and N) algorithm to determine if the point-sets are ...
1
vote
1answer
68 views

Find equation of line without using division

I need an algorithm to find equation of a line without using division. Given a line by two points on it, with coordinates: $(x_1, y_1),\ (x_2, y_2)$. We can simply get the line equation by the ...
0
votes
1answer
34 views

Using cartesian coordinates how to get the segment overlapping two lines/segments?

There must be an algorithm to find the coordinates of the segment overlapping (fully or partially) two lines/segments but my googling does not produce any significant result. Maybe I don't use the ...
0
votes
0answers
32 views

Is there a way to compute the empty area between a group of touching polygons?

Given a bunch of convex polygons layed out like a house truss, is there a way to compute the empty area, or get a polygon for each of those "holes" between the polygons? I tried starting from any ...
1
vote
1answer
50 views

T-shaped polygons

Is there any coefficient that can indicate T-shaped polygons ? Examples of T-shaped polygons:
2
votes
0answers
101 views

Best closed convex surface fitting N points in 3D

First. It's easier to understand the problem by describing the application where it arises from. We have a convex body $B$ in $\mathbb{R}^{3}$ and measure points on its surface. The measurements are ...
1
vote
2answers
40 views

Point as an element of an affine space vs point as an element of a topological space?

I am searching for the "most natural" definition of a (geometrical/space) point as an element of "something" in mathematics (I am trying to design a small computational geometry library on strong ...
1
vote
0answers
46 views

Computationnal geometry: vector, basis, point and coordinate system?

I am trying to build a small geometrical library in C++, that is mathematically consistent (not so false). The goal here is to construct two concepts: vectors and points. I am not sure that the ...
1
vote
0answers
44 views

How many edges is sufficient to check to prove polyhedron convexity?

Consider the set $\{u_{1}, u_{2}, \ldots, u_{n}\}$ of points on the spere in $\mathbb{R}^{3}$ (i. e. $||u_{i}|| = 1$) and their convex hull C = $Hull(u_{1}, \ldots, u_{n})$. It's obvious that each ...
1
vote
0answers
17 views

Mapping optimal sensor placement problem to Art Gallery Problem

I am trying to design an algorithm for optimal sensor placements in a given area. I researched in this domain and found ...
0
votes
2answers
62 views

How to compute surface normal pointing out of the object

An object has been approximated by a lot of triangles. Given the vertex positions of these triangles, how can I compute the normal of these vertices which pointing outside of the object. I know the ...
-1
votes
1answer
63 views

Rotate the Points on a Plane $P = ax+by+cz + d = 0$ parallel to $z = 0$ plane

I have a plane $P = ax+by+cz + d = 0$ and many points on that plane. I want to rotate $P$ so that it becomes parallel to $z = 0$ plane. Which method should I use? I know that the normal vector of my ...
0
votes
1answer
67 views

Transforming a circle to get a parabola

On http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/geometry/geo-tran.html I am unable to understand the following point Obviously, this transformation sends (x,y,w)=(1,0,1) to (x',y',w') = ...
2
votes
2answers
45 views

How to make sure that a given set of points lie on the boundary of a possible square?

Given a set of integral coordinates , check whether all the points given lie on side of a possible square such that axis of the square so formed lie parallel to both X-axis and Y-axis . Suppose ...
0
votes
0answers
29 views

Surface comparison using the vertex information and normal vectors

I have two point clouds with normal vector information. How can I use the normal vector information to measure the surface similarity of these two point clouds?
0
votes
0answers
15 views

Is there a well known algorithm for efficiently computing the vertices of a convex polytope?

A convex polytope, the one I'm talking about, is the hull around all points $x$ satisfying the matrix equation $Ax = b$ and $x \geq 0$. I've been digging around old papers from the 60's and 70's ...
3
votes
2answers
66 views

Finding point on ellipse equally distant from two other points on the ellipse

I have an ellipse with two points on it: A and C (with known coordinates). Point O is the center of the ellipse (coordinates are given). I need to find coordinates of point B which also lies on the ...
0
votes
0answers
67 views

Estimating the geometric shape of a point cloud without using the vertex information

Consider a point cloud format that describes 3D point clouds by vertices, triangle labels and normal vectors. If we miss the vertex information, is it possible to retrieve the lost data by triangle ...
0
votes
1answer
40 views

Desargues Theorem with integer coordinates

Desargues' theorem involves a set of ten points in a plane or in three-dimensional space. (It's true in higher dimensions, but the affine span of the ten points involved never has a dimension more ...
1
vote
1answer
18 views

find set of points for lots of triangulations

I should find a set of $n$ points $Q$ in a plane, so that $t(Q)$ (the number of possible triangulations) the following equation holds: $$t(Q) \ge 2^{n-2\sqrt{n}}$$ I solved the problem using the ...