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

119
votes
22answers
55k views

How to check if a point is inside a rectangle?

There is a point $(x,y)$, and a rectangle $a(x_1,y_1),b(x_2,y_2),c(x_3,y_3),d(x_4,y_4)$, how can one check if the point inside the rectangle?
20
votes
6answers
3k views

Is it possible to solve any Euclidean geometry problem using a computer?

By "problem", I mean a high-school type geometry problem. If no, is there other set of axioms that allows that? If yes, are there any software that does that? I did a search, but was not able to ...
17
votes
1answer
2k views

Geometry of nose in and nose out parking in parking lots

I would like some computational evidence in favor of my observation that one can park a car in tighter (parking lot) spaces by backing in rather than nose in. I have been doing this successfully for ...
13
votes
1answer
176 views

Automorphism group of a lattice's Voronoi cell

Let $\Lambda$ denote a lattice of $\mathbb{R}^n$, i.e. $$\Lambda = \left\{\sum_{k=1}^n n_i\mathbf{a}_i\ \bigg|\ n_i\in\mathbb{Z}\right\},$$ for $n$ linearly independent vectors $\{\mathbf{a}_i\}$ in $\...
12
votes
3answers
7k views

How to Union Many Polygons Efficiently

I've asked this question at SO, but only answer I got is a non-answer as far as I can tell, so I would like to try my luck here. Basically, I'm looking for a better-than-naive algorithm for the ...
12
votes
3answers
213 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 ...
12
votes
2answers
274 views

“Surface Area” of $k$ simplex in $\mathbb{R}^{k}$?

Consider the $k+1$ vertices $(x_1,\ldots,x_{k+1})$ with $x_i\in\mathbb{R}^k,i=1,\ldots,k+1$. I know that the "volume" of the $k$-dimensional simplex formed by these vertices is proportional to $$\...
11
votes
2answers
12k views

Point closest to a set four of lines in 3D

Given four lines in $3D$ (represented as a couple of points), I want to find the point in space which minimizes the sum of distances between this point and every line. I'm trying to find a way to ...
11
votes
2answers
3k views

arc-arc intersection, arcs specified by endpoints and height

I need to compute the intersection(s) between two circular arcs. Each arc is specified by its endpoints and their height. The height is the perpendicular distance from the chord connecting the ...
10
votes
4answers
2k views

Every polygon has an interior diagonal

How does one prove that in every polygon (with at least 4 sides, not necessarily convex), that it is possible to draw a segment from one vertex to another that lies entirely inside the polygon. In ...
10
votes
4answers
3k views

Find whether two triangles intersect or not in 3D

Given 2 set of points ((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) and ((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) each forming a triangle in 3D space. How will you find out whether these triangles intersect or not? ...
10
votes
2answers
133 views

Efficient method for detecting a convex body in $\mathbb{R}^n$

Let $K_0$ be a bounded convex set in $\mathbf{R}^n$ within which lie two sets $K_1$ and $K_2$. Assume that, $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$. The boundary between $K_1$ and $K_2$ is ...
9
votes
3answers
738 views

Unique characterization of convex polygons

Question I am looking for a unique characterization of a convex polygon with $n$ vertices, relative to a feature point $p$ in the interior of the polygon. This characterization would be a vector of ...
9
votes
1answer
771 views

“Cut” (hexagon-like) Reuleaux triangle area

Let me start by giving the reason my question: as part of a 3D printer I'm building (Rostock), I'm trying to figure out the work area of the printer. The printer consists of 3 arms, each attached at ...
9
votes
0answers
72 views

Solving general (dis)entanglement puzzles

What is the state of the art in (modelling and) solving a general (dis)entanglement puzzle? The following picture shows a nice example: There is a project called "The Untangler", which seems to be ...
9
votes
1answer
307 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 ...
8
votes
5answers
7k views

Find the area of overlap of two triangles

Suppose we are given two triangles $ABC$ and $DEF$. We can assume nothing about them other than that they are in the same plane. The triangles may or may not overlap. I want to algorithmically ...
8
votes
2answers
197 views

How to check if polylines can be untangled?

In a program I'm writing I need to be able to check whether a straight line between two points is homotopic to a polyline between them. For example in the below example the first one is equivalent to ...
8
votes
2answers
375 views

Number of distinct nets of dual polyhedra

There are 11 non-congruent nets of a cube as well as 11 distinct nets of an octahedron. Both a dodecahedron and an icosahedron have 43380 distinct nets. Is it true that any pair of dual convex ...
8
votes
2answers
364 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 ...
8
votes
2answers
456 views

Odd fractal-looking illusion with $x,y,z \in [0,1]$ such that $x+y+z=1$, what is wrong?

Thanks to comments, it should be a plane but why does it look a bit like a fractal? Does my code overlook something or some err in plotting tool? I used Python and GNUplot. Apparently an animated ...
8
votes
1answer
488 views

Space filling with circles of unequal radii

Here is my problem: I have a bunch of circles that I need to display inside a canvas. There are an arbitrary number of circles, each with a predefined radius. The summed area of circles is always ...
8
votes
0answers
96 views

How to measure the irregularity of a hexagon?

I need to evaluate the quality of a list of machine parts, which roughly has one center point surrounded by 6 exterior points. If the quality is good, then the 6 exterior points will form a regular ...
7
votes
2answers
327 views

Tiling pythagorean triples with minimal polyominoes

Given a Pythagorean triple $(a,b,c)$ satisfying $a^2+b^2=c^2$, how to calculate the least number of polyominoes of total squares $c^2$, needed, such that both the square $c^2$ can be build by piecing ...
7
votes
2answers
153 views

How to determine whether a point is inside a closed region or not?

Take the following parametric equation of an implicit curve as an example: $$ \left\{\quad \begin{array}{rl} x=& 9 \sin 2 t+5 \sin 3 t \\ y=& 9 \cos 2 t-5 \cos 3 t \\ \end{array} \right. $$ ...
7
votes
7answers
2k views

Detect when a point belongs to a bounding box with distances

I have a box with known bounding coordinates (latitudes and longitudes): latN, latS, lonW, lonE. I have a mystery point P with ...
7
votes
1answer
224 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 ...
7
votes
1answer
207 views

Find the Volume Enclosed by Terrain and a Certain Sea Level

I have a terrain, which is represented by one mesh with a lot of polygons as shown below: This terrain will be cut by a plane at a certain level. So there are volumes of the terrains that are ...
7
votes
0answers
83 views

Fast search of local positive quadruples on the sphere

Let $U = \{u_{1}, u_{2}, \ldots, u_{n}\} \subset \mathbb{R}^{3}$ be the finite set of points on the unit sphere in $\mathbb{R}^{3}$: $||u_{i}||_{2} = 1$ Definition: Quadruple of points $(u_{i}, u_{j},...
6
votes
2answers
1k views

Determine if the coordinates of a point are within an irregular quadrilateral whose corners are defined by coordinates

Given four coordinates that define the corners of an irregular quadrilateral and a point defined by its coordinates, what is the simplest way to determine if the point is within or outside of the ...
6
votes
4answers
864 views

How to know location of a point?

I have a circle formed with three given points. How can i know whether another given point is inside the circle formed by previous three points. Is it determinant i need to calculate? Then what are ...
6
votes
1answer
235 views

Efficient algorithm for finding how many times a point is inside the triangles formed by given points

Given n 2D points and a special point p, what would be the best way to find how many times p is inside among those $^nC_3$ triangles formed by the n points.
6
votes
3answers
105 views

Algorithm to determine if a collection of unit discs covers the unit disc centered at the origin?

I have a list of points $ (x_i, y_i) $ for $i = 1...n$. Is there an algorithm to determine if the union of the unit discs centered at these points is a superset of the unit disc centered at $(0, 0)$? ...
6
votes
2answers
375 views

Test for intersection of two N-dimensional ellipsoids

Let's say I have two $N$-dimensional ellipsoids: $$ \sum_{i=1}^{N} \frac{(x_i - b_i)^2}{c_i^2} = 1 $$ $$ \sum_{i=1}^{N} \frac{(x_i - b'_i)^2}{c_i'^2} = 1 $$ How can I tell if the two ...
6
votes
3answers
445 views

Way to measure the similarity/difference of 2D point clouds

i need a way to measure the similarity or difference of two point clouds? The number of points in each point cloud can be different. The Point clouds are already aligned. By similarity I mean the ...
6
votes
2answers
271 views

Voronoi Diagrams Proof

I am having a real problem with this proof about voronoi diagrams: Prove that $V(p_i)$ (i.e., the cell of $\operatorname{Vor}(P)$ which corresponds to $p_i$) is unbounded if and only if $p_i$ is on ...
6
votes
1answer
207 views

Constructive algorithm for Minkowski's theorem.

There is a theorem of Minkowski that says that given $k$ unit vectors $x_i$ that span $\mathbb{R}^n$ and $k$ positive real numbers $a_i$ such that $\sum_{i=0}^k a_i x_i = 0$ then there exists a unique ...
6
votes
2answers
705 views

“Concave hull” - Possible? Feasible? Deterministic?

So there are several questions regarding how to compute the convex hull of a set of points. However, let's say that on inspection the set of points inscribed a star shape. A Convex hull algorithm ...
6
votes
1answer
234 views

Correlations between neighboring Voronoi cells

For a sequence $X_1,X_2,X_3,\ldots$ of random variables, what it means to say $X_1$ is correlated with $X_2$ is unambiguous. It may be that the bigger $X_1$ is, the bigger $X_2$ is likely to be. If, ...
6
votes
2answers
535 views

Algorithm for positioning rectangles of various size into a larger rectangle

I am working on tool for merging smaller textures into one larger for use on Android app. I have $n$ rectangles of given size $(w_k, h_k)$, where $k=1,\ldots,n$ and I need to position them within ...
6
votes
1answer
138 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 ...
6
votes
1answer
160 views

How to check if a polytope is a smooth Fano polytope?

Question: We say that a convex lattice polytope $P\subset \mathbb{R}^d$ is a smooth Fano polytope if: The origin is contained in the interior of $P$ The vertices of every facet of $P$ are a $\...
6
votes
2answers
139 views

Find the most vertical line in a point set in $O(n \log n)$ time

Input: a set of $n$ points in general position in $\mathbb{R}^2$. Output: the pair of points whose slope has the largest magnitude. Time constraint: $O(n \log n)$ or better. Please don't spoil the ...
6
votes
2answers
681 views

Solving geometric problems using Linear Programming

Is it possible to find an LP formulation to test whether $n$ points in the plane are in convex position?
6
votes
0answers
155 views

Balanced, center-free set. [closed]

We say that a finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC=BC$. We say ...
6
votes
2answers
126 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 ...
6
votes
0answers
118 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$. (...
6
votes
0answers
157 views

Biggest ball included in an intersection of balls

I would like to prove that for any family of balls $\{B(c_i,r_i)\}_i \subset \mathbb{R}^d$ such that $\{c_1, \dots, c_n\} \subset \bigcap_i B(c_i,r_i) $ and $\forall i, r_i \geq 1$, there exists a ...
6
votes
0answers
216 views

Expected Number of Convex Layers and the expected size of a layer for different distributions

It is well-known that the expected number of vertices on the convex hull of random set of points in the plane distributed uniformly within a $k$-gon is $O(k\log n)$ and within a smooth shape (e.g. a ...
5
votes
3answers
548 views

Is it always possible to simply expand a simple 2D polygon with any point?

Given a simple 2D polygon P = ( M1 .. Mn ) and a point M, is it always possible to construct a new simple polygon P' by "adding" M to P as a new vertex? If so, is this always possible without ...