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 ...
60
votes
18answers
5k views
How to check if a point is inside a rectangle?
There is a point (x,y), and a rectangle a(x1,y1),b(x2,y2),c(x3,y3),d(x4,y4), how can one check if the point inside the ...
14
votes
1answer
546 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 ...
12
votes
5answers
945 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 ...
8
votes
2answers
1k 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 ...
8
votes
4answers
984 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
1answer
228 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
118 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
4answers
364 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 ...
7
votes
2answers
208 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
3answers
404 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 ...
7
votes
1answer
196 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
2answers
262 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
345 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
289 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
151 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
2answers
407 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
137 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
175 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
2k 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 ...
5
votes
3answers
82 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
1answer
111 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
2answers
238 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
117 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
46 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
336 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?
4
votes
3answers
207 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
89 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, ...
4
votes
1answer
118 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
134 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
2answers
1k 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
385 views
Turning radius of a vehicle
What's the minimum turning radius of a vehicle, rectangular in shape, with length l units and width w units? One key point to consider, would be that, the inclination of the front wheels can be ...
4
votes
0answers
73 views
How many points does one need for an epsilon-net
Does anyone know, how many points does one need to have an $\varepsilon$-net on a unit sphere sitting in the three-dimensional Euclidean space? Thanks!
4
votes
0answers
114 views
Convex hull of balls
The convex hull is defined as the smallest convex set containing a set of points. Now we want to generalize it to a set of balls. If these balls have the same radius, then it can be shown that a ball ...
4
votes
0answers
348 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
0answers
236 views
$3$D oriented bounding box optimization
Given: a set $S$ of points in $\mathbb{R}^3$.
Find: the smallest oriented bounding box that contains all the points. Note, the bounding box is "oriented" and thus need not be axis-aligned.
Can this ...
3
votes
2answers
144 views
How do I prove that the following method to find whether a point lies within a polygon is correct?
I came across the following method to determine whether a given point lies inside a convex polygon - however, I'm not sure how to prove it.
Given any three points on the plane $(x_0,y_0)$, ...
3
votes
3answers
374 views
Studying the envelope of a family of circles.
This is an exercise on page 150 of Cox/Little/O'Shea's Ideal, varieties and algorithms: an introduction to computational algebraic geometry and commutative algebra, 3rd ed.
I get lost in this ...
3
votes
4answers
1k 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 ...
3
votes
2answers
88 views
How do I apply a digital filter to points on a sphere
Given a set of points on a sphere, how can I implement a higher order low pass filter on them?
At the moment, I am just multiplying the vectors from the input and output set by their weights and ...
3
votes
1answer
230 views
What is the meaning of “unitize a vector”?
The expression "to unitize a vector" is often use in computational geometry. What does it mean?
3
votes
1answer
162 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 ...
3
votes
2answers
202 views
What is the average rotation angle needed to change the color of a sphere?
A sphere is painted in black and white. We are looking in the direction of the center of the sphere and see, in the direction of our vision, a point with a given color. When the sphere is rotated, at ...
3
votes
1answer
217 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 ...
3
votes
1answer
211 views
Ellipse center with three points and the semi-axis lengths given
Having three given points in the two-dimensional plane and semi-axis lengths $a$ and $b$ of an ellipse, how to determine the center? By construction (the "Euclidean way") or analytic geometry.
3
votes
2answers
69 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 ...
3
votes
1answer
123 views
Finding the virtual center of a cloud of points.
Given:
(latitude, longitude) points $P_1, P_2,\ldots, P_n$.
Presumably, all the points should form a dense cloud. However, noise is possible.
Needed:
The virtual center of the points.
For ...
3
votes
1answer
83 views
Determining position at some point in time
I try to solve the following problem.
On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
3
votes
2answers
121 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$. ...
3
votes
1answer
112 views
Method For Constructing Self Referential Formulas Like Tupper's
Can anyone please explain exactly how formulas like Tupper's self referential formula can be constructed?
I'll like to see the reasoning behind the derivation of such formulas and the steps required ...
3
votes
1answer
117 views
Computing the free-part
I wanted to ask about some existing algorithms for computing points over elliptic curves.
Background : We know that the famous theorem of Mordell and Weil says that " Group of rational points on an ...
