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

83
votes
20answers
22k 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?
16
votes
1answer
1k 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 ...
15
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 ...
12
votes
3answers
159 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 ...
10
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 ...
10
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? ...
9
votes
4answers
901 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 ...
9
votes
3answers
633 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
527 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
2answers
128 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 ...
8
votes
3answers
4k 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 ...
8
votes
2answers
156 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
275 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
224 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
1answer
320 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 ...
7
votes
2answers
296 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
406 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 ...
7
votes
7answers
1k 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
175 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 ...
6
votes
2answers
934 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
4k 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 ...
6
votes
4answers
703 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
203 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
93 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
255 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
2answers
117 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
169 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
1answer
157 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
386 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
80 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
2answers
181 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: ...
6
votes
1answer
142 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
93 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
501 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
2answers
54 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
78 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
170 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 ...
6
votes
1answer
205 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 ...
5
votes
3answers
321 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 ...
5
votes
1answer
59 views

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 ...
5
votes
1answer
81 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 ...
5
votes
1answer
960 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 ...
5
votes
0answers
471 views

Segment Tree vs Interval Tree

Segment trees and interval trees both answer stabbing queries about line segments. In 1D, they both take $O(n \log{n})$ preprocessing time and $O(\log{n} + A)$ query time where n is the number of line ...
4
votes
1answer
234 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
283 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
456 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 ...
4
votes
2answers
109 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
152 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
179 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
177 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 ...