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

6
votes
1answer
205 views

How to determine surface from given normal vectors and their distance on that surface

Situation: We have a bendable, non-stretchable surface, like a piece of cloth, with a regular grid on it. Unknown manipulation of the surface is done while preserving it's structure We recieve 3 ...
3
votes
1answer
86 views

Computing with graphs in surfaces

I am currently working on a research project involving a polynomial defined for graphs in surfaces, similar to the Tutte polynomial, except with terms accounting for the embedding. At the moment, it ...
2
votes
1answer
61 views

Modify the closest-pair algorithm to use the $L_\infty$ distance.

I'm trying to understand the closest pair of points problem. I am beginning to understand the two-dimensional case from a question a user posted some years ago. I'll link it in case someone wants to ...
2
votes
1answer
71 views

A method to test for uniform distribution over a convex polytope

Assuming I have a convex polytope defined as the intersection of $Ax=b$ and $x>0$ and I have a way to sample points from this object, is there a way I can test for uniformity of these sampled ...
1
vote
1answer
37 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
107 views

Optimal bounding boxes selection for $N$ rectangles

Suppose that I have $n$ straight rectangles on a plane $r_i = (x_i,y_i,w_i,h_i)$. Each rectangle has a cost function, its area $A(r_i) = w_i \cdot h_i $. I can also "merge" 2 or more rectangles into ...
1
vote
0answers
60 views

Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1, \ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors, assumed affinely independent (in the field of reals). Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ ...
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 ...
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 ...
1
vote
0answers
40 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
0answers
59 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 ...
1
vote
0answers
135 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 ...
1
vote
0answers
346 views

differentiation of polygons, having cross borders

I have point data set and I segmented the data into different planar objects. after that, using contouring (convex hull), I obtained the boundary points. Please assume all points relevant to one ...
1
vote
0answers
36 views

How to discuss the maximum Area of Internal rectangular in an irregular region?

How to discuss the maximum Area of Internal rectangular in an irregular region? such as Fan-shape,or the region....
1
vote
0answers
104 views

The orientation of a closed discrete curve embedded in a triangle.

The two triangles $xyz$ and $x^{\prime}y^{\prime}z^{\prime}$, shown below, have opposite orientations. A closed curve $abcd$ is embedded in the first triangle ($abcd$). The vertices of the ...
1
vote
0answers
266 views

Line comparison algorithm advice

Line is array of points (2 or more). I have a plane full of lines. For a given line in plane I need a measure which will tell how much difference there is between this and any other line in plane. I ...
1
vote
0answers
75 views

Questions about interpolating translated points from a grid

I would like to do the following transformations on a very low resolution bitmap (64x64 pixels). I am doing this transformation on a computer images, but it has nothing to do with computers, you can ...
1
vote
0answers
143 views

Nonlinear least squares and polygon area

I found this paper that describes preserving the global area of a polygon given some deformation (section 5): http://www.kunzhou.net/publications/2DShape.pdf I'm trying to do something very similar. ...
1
vote
0answers
102 views

Complexity of Counting the number of inducing $n$-gons

Definition: A $n$-gon is simple if it has no self intersection and is in general position if no pair of its edges are parallel. It is clear that by extending the edges of each simple $n$-gon in ...
0
votes
0answers
16 views

Visible objects from a point in a polygon with holes in 2d

The problem is the following: Given a polygon P with h holes/objects and a point c inside P but outside the holes/objects. P has n given vertices and each hole/object h has 4 vertices (the ...
0
votes
0answers
37 views

Mathematical proof to find the length of each side of a square filled with Regular Hexagons

I have to prove or disprove that in a square box if there are full regular hexagons( whose distance from center to every corner is r) inside it, then the centers of those hexagons should lie inside ...
0
votes
0answers
10 views

Proof of spherical Helly's theorem

I need to prove that if every three members of a system of convex sets on the surface of a sphere intersect, every member fits in some hemisphere and no four members cover the whole sphere, then the ...
0
votes
0answers
21 views

Maximal area intersection of half-planes in $\mathbb{R}^2$

Suppose we have $m$ half-planes $H_1,...,H_m$ in $\mathbb{R}^2$ such that $H_1 \cap \dots \cap H_m = \emptyset$. Let $A$ be a set of subsets $S$ of $\{H_1,...,H_m\}$ with non empty intersection and ...
0
votes
0answers
28 views

Find points that defines the intersection of an ellipse with a plane.

I want to test for the intersection of two ellipses $E_1$ and $E_2$ in $\mathbb{R}^3$ represented on a computer. In some sense, this isn't a hard problem: ...
0
votes
0answers
48 views

Algorithm to optimize rectangles filling by rectangles

I have a set of rectangles, all of the same size (W,H) (in fact paper sheets). I have another set of n rectangles of different sizes (Wi,Hi), i = 1..n such that Wi <= W and Hi <= H (in fact ...
0
votes
0answers
43 views

Can a polygon with minimal perimeter self-intersect?

Recipe. Do the following. Throw $N$ random points $(x_0,y_0),(x_1,y_1),x_2,y_2),\cdots,(x_{N-1},y_{N-1})$ in the plane.Define $(x_N,y_N)=(x_0,y_0)$ : enumeration is $\mod N$ . These points are joined ...
0
votes
0answers
16 views

How get the new location of co-planar vertices oriented by the direction vector?

How am I supposed to get the new location of co-planar vertices, if I know the starting and ending point of direction vector, so the direction vector, in spatial space? The original vertices are in ...
0
votes
0answers
37 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 ...
0
votes
0answers
18 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
0answers
46 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 ...
0
votes
0answers
60 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
25 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 ...
0
votes
0answers
26 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
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 ...
0
votes
0answers
31 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
17 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 ...
0
votes
0answers
81 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
0answers
100 views

Find vertex of a parallelogram/parallelepiped/parallelotope with minimum distance to a point

Suppose you have a parallelogram and a point. It's easy to tell which of the parallelogram's vertices is closest to the point (Euclidean distance) by checking the distance for every vertex - but this ...
0
votes
0answers
36 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
0
votes
0answers
145 views

how to get optimal vector, which is parallel to intersection line of many plane (Least Square way)

My idea is to construct the best optimal 3D line representing the intersection of many 3D planes. (As we know, due to fitting errors or data errors, the fitted planes might not intersect exactly ...
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 ...
0
votes
0answers
69 views

Plot randomly oriented gaussian kernel

I would like to plot with scipy randomly oriented gaussian kernels. For a gaussian kernel along x and y axis (with an angle 0 w.r.t. coordinate system), I simply plot function ...
0
votes
0answers
226 views

Algorithm for intersection between polyline and rectangle?

My problem is simple, and probably obvious from the title itself, but I'll still clarify it a bit: I have a rectangle and a polyline (array of N connected points). I need an optimal algorithm that ...
0
votes
0answers
67 views

Sufficient conditions for “2-sphericity” of orientable triangulated 2d surface in 3d space

Let $T$ be finite set of tetrahedrons in $\mathbb{R}^3$. Let $T$ be tetrahedral complex in a sense that if two tetrahedrons intersect, the intersection is a face of both. Let $\partial T$ consist of ...
0
votes
0answers
157 views

Decomposition of multidimensional point set

I am trying to use point sets to define the subdivisions of a multidimensional space and use a hash table to store the subvisions. This approach requires decomposing the multidimensional space into ...
0
votes
0answers
115 views

polygon inside a polygon

i have several point patches lie on different planar faces. then, I obtained enclosing polygons to represent points so that i have several planar polygons (for example A,B,C,D). when i examine the ...
0
votes
0answers
94 views

Does a single Gauss-Seidel iteration lead to unique coordinates?

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$, and $x,y\in\mathbb{R}^{n\times 2}$ are ...
0
votes
0answers
86 views

Can 2 parallel lines be discriminated as 'away', 'beside' with respect to 3rd parallel line?

I have nearly parallel several 3D line segments. some line segments locate (blue line) beside to a spefic line segment (black line) and some other (red line) locate away from that line segment. i want ...
0
votes
0answers
49 views

Maintaining the line with the 2D iterands

Suppose a linear system is given $$AX=B,$$ where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is ...
0
votes
0answers
77 views

How to interpolate sequential points to obtain functions and/or vectors?

I would like to know how I can interpolate a sequence (time) of points in order to obtain curves as some kind of mathematical functions. Unfortunately math is not my area so I don't really know the ...