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
0answers
28 views

finding quadilaterals from given sides

I have a set of Points. I triangulated the Points as delaunay triangles but i only have edges for the triangles means edge array of the whole set of Points. Now i need to find the traingles and ...
5
votes
2answers
46 views

Simplest graph that is not a segment intersection graph

Given a finite collection $S=\{s_1,s_2,\ldots,s_n\}$ of straight-line segments in the plane, their intersection graph $G(S)$ is a graph that contains a vertex $v_i$ for each segment $s_i\in S$, and an ...
0
votes
0answers
7 views

Optimized collision check for all pairs using bounding volume hierarchy

I am working on broad-phase collision detection. I understood how to build a bounding volume hierarchy using AABB's as bounding volumes. I also understood how to check all collisions of a single AABB ...
0
votes
1answer
20 views

Divide set of points by a plane so sum of distances of points on either side of plane is equal

I have a finite set of points A and another point C. I would like to compute a vector N so that the plane defined by C (point on plane) and N (normal of plane) divides all points in A with the sum of ...
0
votes
1answer
34 views

Cut the Cake into 4 parts

I'm facing the following problem: I'm given a set of coordinates on an integer grid that define the vertices of a polygon. The polygon is guaranteed to be convex. It's proven that such a polygon can ...
0
votes
0answers
16 views

Existence objective function given optimality regions

Let $I$ and $X$ be finite, nonempty sets, and denote by $\Delta(X)$ the set of probability measures on $(X,2^X)$. Suppose that for each $i \in I$, we are given a subset $M_i \subseteq \Delta(X)$ of ...
0
votes
1answer
41 views

Term For Rotating 3d Vectors About a Pivot Point

What is the term for Rotating a 3d Vector about another 3d Vector (Pivot Point)? For example; if I want to move X distance from one point towards another point - the mathematical term for this ...
1
vote
1answer
15 views

What's wrong with this pseudocode for Forster-Overfelt's version of the Greiner-Horman polygon clipping algorithm?

The Problem I'm trying to understand and implement the Forster-Overfelt version of the Greiner-Horman polygon clipping algorithm. I've read the other Stackoverflow post about clarifying this ...
1
vote
0answers
24 views

Research scopes in Computational Geometry

I have taken a short a course on Computational Geometry and at present I want to do some research works of my own. Can anybody tell me about the research scopes on it? I mean, what are the active ...
-1
votes
1answer
52 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
34 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 ...
3
votes
1answer
71 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 ...
0
votes
1answer
22 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
18 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
49 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
18 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
83 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
37 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
60 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
70 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
39 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
42 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
35 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
56 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
202 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
51 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
117 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
48 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
22 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
32 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
84 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
37 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
69 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
39 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
41 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
49 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
18 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
69 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
65 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 ...