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
vote
0answers
52 views

Winding Number of a Circle

I'm having a little trouble calculating the winding number of a circle about a point using parametric equations. The definition of a circle of radius $r$ and center coordinates $x_0$ and $y_0$ is the ...
1
vote
0answers
20 views

Algorithm detect simple curves using Voronoi diagram or Delaunay triangulation?

I wonder if there is algorithm/method to determine if closed (or even non closed) curve is simple or not, using the mathematics from the field of computational geometry? Especially I wonder if exist ...
1
vote
0answers
17 views

Is this projection optimization problem NP-hard?

Suppose we are working in ${\mathbb R}^d$ (dimension is not fixed), and we have a set of $n$ points $X = \{x_1,\ldots,x_n\}$ in that space. Given a query point $y$ inside the convex hull of $X$, we ...
1
vote
0answers
34 views

Epipolar geometry - Fundamental matrix derivation (Hartley, Zisserman)

I have a question to the following derivation of the fundamental matrix by Hartley and Zisserman in "Multiple View Geometry in computer vision" (Link, page 5): Why is it possible to do the very ...
1
vote
0answers
99 views

Find the intersection between two convex hulls, in this specific case

We work over $\mathbb{R}^K$. Let $V$ the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$, . Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
1
vote
0answers
23 views

Find largest regions bounded by a set of planes

Suppose we are given a set of planes that partition the unit cube into a large number of regions. Is there a computationally efficient way to find the region with the largest volume?
1
vote
0answers
84 views

Understanding BlowUp Computation in Singular

Many of us might know that "Singular" is a computer algebra system for Algebraic Geometry, Commutative Algebra and Non-commutative algebra. This is a procedure in "Singular" for computing blowups. ...
1
vote
0answers
62 views

population of dots with normal distribution of pitch

I want to generate a plot that shows a rectangle populated with dots, where the dot-to-dot distance (pitch) distribution is a lognormal (or a gaussian). I want to be able to change the mean dot-to-dot ...
1
vote
0answers
28 views

Finding other two vertices when one vertex and each point on the triangle is known ?

I am working on some gesture recognition for my game. I am stuck on a problem. I have one vertex i.e the starting point and every point on the triangle, I also have the centroid. So how do I find the ...
1
vote
0answers
32 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
1
vote
0answers
75 views

Find 3D concave hull based on original model and convex hull

I want to find the concave hull of a 3d model, with a threshold for the maximum edge size. Googling around let me to the following approach (mainly abstracting from 2d approaches): Determine the ...
1
vote
0answers
19 views

ellipsoid and paraboloid relation

My task was to programme a paraboloid and an ellipsoid. I implemented paraboloid as a set of points that's distance from the focal point and the distance from the plane is the same. After running the ...
1
vote
0answers
198 views

How to Compute the Torsion and Curvature of a Parametric Curve

So I have a parametric curve $\bf{r}=${$x(n),y(n),z(n)$} such that the functions $x(n)$, $y(n)$ and $z(n)$ are polynomials of $4$-th degree. I have several of these curves, and I want to calculate the ...
1
vote
0answers
596 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 ...
1
vote
0answers
20 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′).
1
vote
0answers
72 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
32 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 ...
1
vote
0answers
37 views

Geometric accuracy analysis of 2d rectangular models

I have reconstructed set of rectangular objects lie on a 2D plane (for ex. ABCD). All these objects are in a one coordinate system. On the other hand, I have reference models for all of them ...
1
vote
0answers
51 views

Background required for Computational Geometry

I am hoping to enroll in Computational Geometry course this spring. This was the textbook used for the course in the past. I am trying to figure out if I have required math background for this ...
1
vote
0answers
32 views

sweeping edges till they get a given elevation on an oblique plane

I am constructing wireframe model of 3d objects (prisms,..etc.). from a triangular mesh, I have obtained boundary points and fit striaght lines in order to get polygon edges refering to prism ...
1
vote
0answers
215 views

Formula for intersection of “power” curve and parabola.

EDIT I have edited this question to make it more clear. I have spent quite some time trying to find this on Google, but haven't succeeded. I need the formula(s) to determine the intersection ...
1
vote
0answers
39 views

Length of the voronoi diagram

Does there exist an algorithm for computing the length of the voronoi diagram of a set of points or just gives the intersection points of the voronoi diagram?
1
vote
0answers
70 views

largest polygon from segments

There is a set of segments. and I want to calculate the area of the largest polygon which can be build using these segments. I try to search it, but I can't find anything. thanks
1
vote
0answers
231 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
40 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 ...
1
vote
0answers
93 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
60 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
47 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
66 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
157 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
307 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 ...
1
vote
0answers
143 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 ...
1
vote
0answers
417 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
117 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
423 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
84 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
164 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
89 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 ...
1
vote
0answers
107 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
11 views

Computing the approximate area of an iso surface

I'm searching for an approximation to the surface area of isosurfaces. They are defined by a constant value v in a scalar field. The scalar field is defined by placing n vectors in k-space such that ...
0
votes
0answers
5 views

3D mesh segmentation simple algorithm

I am developing the algorithm reported in this article: Lest square conformal mapping Here is presented an algorithm to flat a 3d mesh on the parametric space, but i don't understand the ...
0
votes
0answers
20 views

Subdivisions and Triangulations of Polytopes

Using one of the algorithms proposed in the chapter, triangulate the set P = P1/P2, where P1 is a hexagon given by vertices f(2; 0); (1; 2); (􀀀1; 2); (􀀀2; 0); (􀀀1;􀀀2); (1;􀀀2), and P2 is a square ...
0
votes
0answers
12 views

Proof for non-tetrahydralizability of Schonhardt polyhedron

It is established that not all polyhedrons are tetrahydralizable. Schonhardt's polyhedron is the simplest example for it. I was reading the proof for this given in the book "Art Gallery Theorems and ...
0
votes
0answers
13 views

Intersection Multiplicity of Rational Plane Curves

Suppose I have two rational curves in the complex projective plane. I know their parametrizations, $<x_1(t),y_1(t)>$ and $<x_2(t),y_2(t)>$ I know I can use Grobner bases to find an ...
0
votes
0answers
15 views

C /matlab/ Algorithm for monotonicity of Ploygon

is there any easy and understand able algorithm to check the monotonicity of random polygon and also help me to code in which language(c or matlab) is beneficial to code the algorithm
0
votes
0answers
12 views

Most efficient way of transforming from V-representation to H-representation

What is an efficient way to transform from the v-representation of a convex hull (in terms of vertices) to its h-representation ($Ax \leq b$)?
0
votes
0answers
76 views
0
votes
0answers
42 views

Area swept out by a moving polygon

Say you've got a polygon (say a quadrilateral) that is moving along a certain known path in a plane. The polygon may be changing in shape as it moves, however you know the paths of each of the ...
0
votes
0answers
12 views

Reference request: quantifying qualities of a bunch of points using statistics derived from their Delaunay triangulations

I am interested in using Delaunay Triangulations (DTs) to explore the statistics of a cluster of points. Here's an example cluster of points $P$, with its $DT(P)$ (for now, ignore the difference in ...