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

78
votes
20answers
17k 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?
15
votes
1answer
997 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
5answers
1k 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 ...
11
votes
3answers
156 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 ...
9
votes
2answers
2k 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 ...
9
votes
4answers
2k 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? ...
8
votes
4answers
774 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 ...
8
votes
2answers
188 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
3answers
537 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 ...
8
votes
1answer
477 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 ...
8
votes
2answers
125 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 ...
7
votes
2answers
150 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 ...
7
votes
2answers
263 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 ...
7
votes
1answer
297 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 ...
6
votes
3answers
3k 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 ...
6
votes
2answers
291 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 ...
6
votes
2answers
396 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 ...
6
votes
7answers
864 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 ...
6
votes
1answer
170 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 ...
5
votes
4answers
3k 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 ...
5
votes
2answers
853 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 ...
5
votes
4answers
684 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 ...
5
votes
1answer
197 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.
5
votes
3answers
91 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)$? ...
5
votes
2answers
238 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 ...
5
votes
2answers
114 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 ...
5
votes
1answer
160 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 ...
5
votes
1answer
141 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, ...
5
votes
2answers
361 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 ...
5
votes
1answer
63 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 ...
5
votes
2answers
167 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: ...
5
votes
1answer
137 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 ...
5
votes
2answers
89 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 ...
5
votes
2answers
472 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?
5
votes
0answers
67 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$. ...
5
votes
0answers
164 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
1answer
200 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 ...
4
votes
3answers
308 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 ...
4
votes
1answer
847 views

Star-Shaped polygons

We call a polygon star-shaped if there exists at least one point for which the entire polygon is "visible" from that point. The set of such points we call the kernel of the polygon. The art-gallery ...
4
votes
1answer
218 views

How to predict the tolerance value that will yield a given reduction with the Douglas-Peucker algorithm?

Note: I'm a programmer, not a mathematician - please be gentle. I'm not even really sure how to tag this question; feel free to re-tag as appropriate. I'm using the Douglas-Peucker algorithm to ...
4
votes
3answers
265 views

Average degree of convex hull vertices in a Delaunay triangulation

Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. ...
4
votes
2answers
106 views

Convex sets: a hint on how to solve a problem

Could anyone give me a hint on how to solve the following problem? Let $X_1, \dots, X_{d+1}$ be some finite sets in $\mathbb{R}^d$, such that the origin lies in ${\rm conv}(X_i)$ for all $i \in \{1, ...
4
votes
1answer
139 views

Shortest path in polygonal domain

The single shot query for the shortest path between two points in a plane environment with polygonal obstacles of complexity $O(n)$ can be solved in time $O(n \log n)$ using the continuous Dijkstra ...
4
votes
1answer
171 views

Determine if circle is covered by some set of other circles

Suppose you have an existing set of circles $\mathcal{C} = {C_1, .., C_n}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius ...
4
votes
1answer
164 views

Convex hull problem with a twist

I have a 2D set and would like to determine from them the subset of points which, if joined together with lines, would result in an edge below which none of the points in the set exist. This problem ...
4
votes
1answer
87 views

Covering all the edges of a hypercube?

Consider an arbitrary $n$- dimensional hypercube: If we select $n - 1$ corners of that hypercube and highlight all $(n - 2)$ dimensional elements that originate from each of the corners is it ...
4
votes
1answer
44 views

How can I geometrically (or geographically) group items together?

I'm a programmer, and I'm working on a project that takes a bunch of photos and separates them into groups by their gps coordinates. I have no experience in things like geometric group theory so I'm ...
4
votes
1answer
134 views

Intersection of planes by forming 3d lines

If I have $n$ known planes (known normal vector and a point on a plane) that intersect each other in such a way so as to form closely located 3D lines, then (1). To get a common single 3D line to ...
4
votes
2answers
2k views

Calculating a tangent arc between two points on two circles

How can I calculate the arc between two circles? The arc must be tangent to the two points on the circles. Here is a picture illustrating it. I'm trying to code and calculate the orange arc and the ...
4
votes
0answers
94 views

Dirichlet's approximation theorem (simultaneous version): proof via Minkowski's theorem

There is a proof of the Dirichlet's approximation theorem based on Minkowski's theorem. The proof is given on wikipedia (http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem) and it is ...