# Tagged Questions

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 ...

939 views

### Is there a formula for the solid angle at each vertex of tetrahedron?

A tetrahedron has four vertices as much as a triangle has three vertices. A tetrahedron therefore can have four solid angles as much as a triangle can have three angles. I am wondering: Is there a ...
1k views

### How to find all intersection points of two splines?

2D-Cubic splines are given in parametric form (X(t), Y(t) and X(s), Y(s)). Every segment has it's own X and Y expression. And I want to find all intersection points. Some segments are intersecting ...
108 views

### find largest cube in lot of cuboids

sorry for my bad English... I've a system consists of many cuboids, many are adjacent to the others. My problem is... I want to find the largest cube in this system (which may consists of many of some ...
533 views

### Set of segments a vertical ray intersects

The problem is 10.6a from Computational Geometry: Algorithms and Applications. We want to solve the following query problem: Given a set $S$ of $n$ disjoint line segments in the plane, ...
36 views

### split a rectangle with triangles into polygons as uniformly as possible

Given a rectangle $A$ and $n$ triangles $\{B_1,B_2,...,B_n\}$, I put the triangles inside $A$, at least one vertex of each triangle is not outside $A$ (inside $A$ or on the edge of $A$). So that A is ...
31 views

### Given a number N, how to construct a set of different numbers that has a maximal product, and the sum of these numbers equal N?

Note that: N is positive integer. The set also consists of positive integers. The set consists of different integers. (The thread suggested by @hardmath doesn't have this constraint.) For example: ...
19 views

### computing the heat kernel for small times

The heat kernel on a two-dimensional manifold $M$ has the well-known expression $$H(p,q,t) = \sum_{i=1}^\infty e^{\lambda_i t}\phi_i(p)\phi_i(q)$$ where $\phi_i, \lambda_i$ are the eigenfunctions and ...
27 views

### Is there an equation/algorithm to find the axis of a curved helix with varying pitch and radius?

I'm trying to find a way to numerically extract or estimate the axis of rotation for an arbitrarily shaped helix, which may be curved and have varying pitch and radius. (See here for an example.) ...
25 views

### Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
35 views

### translate of a homothet of a convex body

Suppose we have given a convex body $K \subset \mathbb{R}^2$. How can we prove that it contains a translate of its homothet $-\frac{1}{2} K$? hint: take three vertices $A, B$ and $C$ of the convex ...
23 views

### Intersection of line with polygon

We have a convex polygon P with n edges and a line L (not a line segment!).You are allowed to do some preprocessing .After preprocessing ,find whether the line intersects polygon in O(logn) time . ...
46 views

### Constructing triangulations algorithmically

I am developing a Python package for computations in algebraic topology (namely: cohomology and Massey products on manifolds). Basically all the stuff I'm doing requires an explicit triangulation of ...
73 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 ...
25 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 ...
18 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 ...
48 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 ...
108 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}_+$ ...
26 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?
76 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 ...
29 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 ...
46 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 ...
81 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 ...
21 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 ...
19 views

### create polygon section with equal sides

I have to create essentially these sections of a polygon. I have width(W) and height (H), and number of sides (3 on left abc and 4 on right image ABCD) I need each side to be equal. How can I achive ...
253 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 ...
21 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â€²).
78 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 ...
37 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 ...
38 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 (for ...
54 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 ...
34 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 faces....
231 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 ...
40 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?
72 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
42 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 ...
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 ...
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 via ...
48 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 ...
69 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 ...
161 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 ...
342 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 ...
147 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 ...
424 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 ...
37 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....
123 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 ...
461 views

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 ...