# Tagged Questions

49 views
+50

### What series of 'hyperpolyhedrons' do exist? Is there an effective way to derive their cross-sections by 3-d subspace?

There are two obvious series of 'hyperpolyhedrons'. 'Hyperoctahedron' with vertices $(\pm1,0...0), (0,\pm1,0,...0)...(0,...0,\pm1)$ and each vertex connected by an edge with each other vertex ...
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 ...
18 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 ...
66 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$ ...
74 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 ...
86 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 ...
38 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 ...
61 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 ...
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 ...
43 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 ...
204 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 ...
52 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$ ...
118 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 ...
33 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. ...
88 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.
39 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 ...
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
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 ...
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 ...
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 ...
50 views

### T-shaped polygons

Is there any coefficient that can indicate T-shaped polygons ? Examples of T-shaped polygons:
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 ...
50 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 ...
46 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 ...
68 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 ...
47 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 ...
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?
70 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 ...
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 ...
36 views

### Room for computational geometry in advanced algorithms course

I am currently putting together an independent study in advanced algorithms and because of my interest in (computational) geometry, wanted to include as many interesting algorithms from this field as ...
32 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 ...
70 views

### Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
72 views

### Problem while constructing Delaunay triangulation

At the moment I'm implementing an algorithm to construct a Delaunay triangulation for a set of points. I'm using the algorithm described in Computational Geometry: Algorithms and Applications. The ...
68 views

### Orthogonal 4-cut of a convex polygon

Given a convex polygon with N vertices I need to cut it into four equal area parts with two straight orthogonal cuts. I feel that I have all the necessary pieces to solve this puzzle, but I can't put ...
53 views

### Convex Combination of Disks

We can define a closed disk $D$ with center $c$ and radius $r$ as the set of points $x$ satisfying $f(x) \le 1$ where $f(x) = \frac1{r^2}\lVert x-c \rVert^2$. Now take two disks $D_0,\,D_1$ with ...
107 views

### 3D Convex Hull and The Gift Wrapping Principle

I am currently trying to implement a 3D convex hull algorithm that is based on the paper Convex Hulls of Finite Sets of Points in Two and Three Dimensions by F.P. Preparata and S.J. Hong, but I’ve run ...
81 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 ...
70 views

### When is a convex polygon inscribable?

Defining the diameter of a convex polygon as the maximum possible distance between all pairs of vertices, can we conclude that the convex polygon is inscribable (i.e has all its sides as chords of a ...
28 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 ...
81 views

### Packingof Spheres in 3D

I am looking to find out the size of the largest sphere , that can fit in the voids created by packing spheres ( hcp) of radius R.
103 views

### Convex hull questions

Suppose I am in D-dimensional space, e.g. D=2. What is the minimum number of points to create a valid convex hull? If D = 2, would I need 3 points to create a convex hull (i.e. to form a triangle)? ...
84 views

### Correcting plane parameters with the fixed azimuth angles

I am trying to reconstruct specific 3d objects such as cubes, pyramids and so on. For this, i am using point cloud data and then fitting planar surfaces for the segmented point patches. Planes ...
189 views

### Ellipse arcs. Draw a tangent line in the end point or make arc longer?

I read this article: link It describes how to draw ellipse arcs at all from svg. Each ellipse is described with the following params (and I know them): x1, y1, x2, y2 - arc from point (x1, y1) to ...
178 views

### Finding the largest circle that contains a single point in a set (and no other point)

Given a bounded $A \times B$ rectangle with a set of chosen coordinates, generated for example with the command: ...
168 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 ...
149 views