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

9
votes
0answers
68 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 ...
1
vote
1answer
40 views

Use Complex Analysis for Finding Reflection of a Point in a Line

In the question Point reflection over a line complex analysis was used. Can anyone tell me if this method is superior to the standard method (find a perpendicular from the point to the line, find a ...
12
votes
2answers
240 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 ...
1
vote
0answers
35 views

translate of a homothet of a convex body

Suppose we have given a convex body $K \subset \mathbb{R}^2$. How can we prove that it contains a translate of its homothet $-\frac{1}{2} K$? hint: take three vertices $A, B$ and $C$ of the convex ...
1
vote
3answers
32 views

Dual set of the unit ball is part of the unit ball.

Define the unit ball centered at the origin as $B=\{x\in\mathbb{R}^d\mid \|x\|\leq 1\}$. Define the dual set of set $X$ as $X^*=\{y\in\mathbb{R}^d\mid\langle x,y \rangle\leq 1\ \forall x\in X\}$. ...
1
vote
2answers
49 views

How can we find the area of the triangle which covers a finite point set in $\mathbb{R}^2$ by using the interior triangles with specified area?

Suppose we have given a finite point set $X \subset \mathbb{R}^2$ in a way that any triangle made by vertices of $X$ has area at most 1. How can we prove that there is a triangle of area 4 which is ...
2
votes
2answers
43 views

do infinite family of lines in $\mathbb{R}^2$ have a common point by knowing that any three of them have common point?

Suppose we have given an infinite family of lines; say $\mathfrak{F}$, in the plane $\mathbb{R}^2$ such that any three of the lines in $\mathfrak{F}$ have a common point. How can we prove that all ...
1
vote
2answers
82 views

Check if a point lies in a circle defined by three other points.

I'm learning Computational Geometry, and need to check whether a point p lies inside a circle defined by a triangle(made by 3 points $a,b,c$, in counterclockwise order). A very convenient method is ...
0
votes
0answers
81 views
1
vote
1answer
27 views

Convex hull of union of polytopes in halfspace representation

Suppose I have two polytopes in $\mathbb{R}^n$ given in H-representation as $P_1: \{x | H_1 x\leq b_1 \}$ $P_2: \{x | H_2 x\leq b_2 \}$ My question is, if it is possible to efficiently (i.e., avoid ...
0
votes
0answers
45 views

Area swept out by a moving polygon

Say you've got a polygon (say a quadrilateral) that is moving along a certain known path in a plane. The polygon may be changing in shape as it moves, however you know the paths of each of the ...
0
votes
0answers
13 views

Reference request: quantifying qualities of a bunch of points using statistics derived from their Delaunay triangulations

I am interested in using Delaunay Triangulations (DTs) to explore the statistics of a cluster of points. Here's an example cluster of points $P$, with its $DT(P)$ (for now, ignore the difference in ...
0
votes
1answer
19 views

How to ensure that a point A(x,y) doesn't cross a imaginary line between two other points.

I'm programming an web app and I need some help with a problem, as my mathematical skills are not great. I have 4 points in an XOY system with the origin in the top left. I need to make sure that any ...
2
votes
1answer
29 views

Determine the locus

Let $0<a<b$. Consider two circles with radii $a$ and $b$ and centres $(a, 0)$ and $(b,0)$ respectively with $0<a<b$. Let $c$ be the center of any circle in the crescent shaped region $M$ ...
2
votes
0answers
29 views

Calculate the shortest continuous path between shapes without passing thru other shapes in a specific order?

I have the following points, shapes and paths I would like to calculate how to go thru: We do not have to move in a diagonal direction if that poses a problem. Here would be the movement with just ...
0
votes
0answers
9 views

Find Maximum Density of Point Set

Suppose I have $n$ 3D points. Given any point $x$, radius $R$, and integer $k \leq n$, I can efficiently return a list of (up to) $k$ points nearest to $x$ and closer than $R$ (i.e. bounded k-nearest ...
1
vote
0answers
22 views

Intersection of line with polygon

We have a convex polygon P with n edges and a line L (not a line segment!).You are allowed to do some preprocessing .After preprocessing ,find whether the line intersects polygon in O(logn) time . ...
0
votes
0answers
23 views

number of points with distance $\ge \delta$ that can fit inside a square with edge length $\delta$

I want to prove the claim that if you have a square with edge length $\delta$ and you want to fit as many points, each pair has distance $\ge \delta$, inside that square, You can fit at most 4, and ...
0
votes
0answers
21 views

Tangent Plane of two polyhedron from below in 3D

The convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. A polyhedron (plural polyhedra or polyhedrons) is a solid ...
0
votes
1answer
46 views

equivalence of theory of reals and Rationals

Present a sentence φ that is in theory of reals but not in thoery of Rationals Following up from this question what is the approach to show that both the theories are equivalent Th(R, 0, 1, +, ≤) ...
0
votes
0answers
24 views

how to find a tetrahedron in $R^n$ to bound an ellipsoid (again in $R^n$)

Assume you are given the following ellipsoid in $R^n$: $E: (c+\sum_{i=1}^n \alpha_ix_i)^2$, where $x_i$ 's are the coordinate variables. c and $\alpha_i$'s are constant. now the question is how to ...
3
votes
2answers
55 views

Distance to a convex hull

I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$. Given a new point $y$, how can I verify that distance from $y$ to the convex hull of $x_i$ is less than a given $\varepsilon$? It's not important for me ...
0
votes
0answers
17 views

Boundary points of a convex hull

I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$. What is an efficient way to get (some) subset of boundary points out of them? Also, if I add a new point to this set, how can I efficiently update this ...
2
votes
2answers
54 views

Test if point is in convex hull of $n$ points

I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$, and I would like to check that some other point $y$ lies in their convex hull. How can I do this in some efficient way? I think that there was an ...
2
votes
1answer
42 views

Fastest computation to find out if two vectors intersect (programming problem)

I'm trying to write a program that should solve a 12x12 rush hour problem: I won't go in the details of this program to much. The program already works for 6x6 puzzles, but for 12x12 puzzles, it is ...
0
votes
0answers
34 views

Rigid circles inside a square

There are $n$ circles each of radius $r$. They are needed to fit into a square with side length $t$ in a way such that, the circles can't move in any direction (each one is adjacent to some other ones ...
7
votes
0answers
85 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 ...
0
votes
2answers
32 views

Center of mass from shape boundary

It is possible to find a shape center of mass by only its boundary? Would the average coordinates of X and Y would approximate my center of mass? (If it would work how good the approximation is going ...
0
votes
0answers
10 views

What line-polygon clipping algorithm can I use to ensure that the resultant endpoints are always within the polygon?

I have a 2D plane, partitioned into n-sided, convex polygons. I'm using WRF's PNPOLY algorithm for polygon inclusion to ensure that a point belongs inside one and only one polygon. Is there an ...
1
vote
0answers
46 views

Constructing triangulations algorithmically

I am developing a Python package for computations in algebraic topology (namely: cohomology and Massey products on manifolds). Basically all the stuff I'm doing requires an explicit triangulation of ...
0
votes
0answers
25 views

Fencing $n$ points while keeping minimum distance $d$ from each point

Consider this problem **I have a land consisting of $n$ trees. Since the trees are favorites to cows, I have a big problem saving them. So, I have planned to make a fence around the trees. I want ...
0
votes
1answer
89 views

Calculate the area of an irregular cyclic convex polygon

I want to write a program in C++ to calculate the area of irregular cyclic convex polygons. However, the inputs are in the form corner point angles. I am just not sure what the inputs mean and what ...
0
votes
0answers
53 views

The number of facets of an affine image

I have a full dimensional polyhedron $P_1 \subseteq \mathbb{R}^d.$ Now i define another polyhedron as follows: $$P_2 = AP_1 \oplus B$$ with $A \in \mathbb{R}^{(d-1) \times d}, \,\, B \in ...
1
vote
0answers
67 views

Winding Number of a Circle

I'm having a little trouble calculating the winding number of a circle about a point using parametric equations. The definition of a circle of radius $r$ and center coordinates $x_0$ and $y_0$ is the ...
0
votes
0answers
17 views

Natural neighbor interpolation

Recently I am interested in Natural neighbor interpolation, that is : Given a function $P(x)$ and some interpolation points $\{x_i,P(x_i)\}_{i=1}^N$, we have the interpolation function ...
2
votes
1answer
21 views

2-d pathfinding around connected walls

In a recently released game, characters navigate (poorly) around a 2d martian surface performing tasks. Just for fun, I am trying to come up with a better algorithm. The problem: Given a set of ...
1
vote
0answers
22 views

Algorithm detect simple curves using Voronoi diagram or Delaunay triangulation?

I wonder if there is algorithm/method to determine if closed (or even non closed) curve is simple or not, using the mathematics from the field of computational geometry? Especially I wonder if exist ...
1
vote
0answers
20 views

Find foci and eccentricity of ellipse given either 5 points or its general equation [duplicate]

I'm considering an arbitrary, non-degenerate ellipse here, i.e., without assuming that it's centred on the origin or either axis, nor oriented at any specific angle. I know either 5 points on the ...
4
votes
0answers
77 views

Affine-regular hexagon in convex body

An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb ...
1
vote
1answer
28 views

Not a polyhedral complex example

I am having difficulty interpreting the definition of a polyhedral complex. Can someone explain it using an example and then walk me through an example which is not a polyhedral complex.
1
vote
1answer
73 views

Shortest polygonal line that connects three disjointing circles

Given three disjointing circles, how to find the shortest polygonal line (consisting of two line segments) that connects the three circles (a line segment connects circle A and B if it starts with ...
1
vote
1answer
33 views

point inclusion in a half-plane 3D

I have a 3D half-plane defined using a line segment an a point (as shown in picture taken from here). I am wondering how I can detect if a point belongs to the half-plane. Is there any way to ...
1
vote
0answers
18 views

Is this projection optimization problem NP-hard?

Suppose we are working in ${\mathbb R}^d$ (dimension is not fixed), and we have a set of $n$ points $X = \{x_1,\ldots,x_n\}$ in that space. Given a query point $y$ inside the convex hull of $X$, we ...
3
votes
3answers
141 views

Check if a point is inside a rectangular shaped area (3D)?

I am having a hard time figuring out if a 3D point lies in a cuboid (like the one in the picture below). I found a lot of examples to check if a point lies inside a rectangle in a 2D space for example ...
0
votes
0answers
46 views

Determining N d-points yielding equal sums of Euclidean distances from M s-points

Given M source points (s-points), determine N, the number of destination points (d-points), and their locations (coordinates), such that the sum of the N Euclidean distances from each source point to ...
0
votes
0answers
35 views

Determing the Two Closest Vertices a Point Lies Between on Circumcircle

For a computational geometry application, I need to determine the two closest vertices that a point lies between on a circle that has been sliced into angular intervals. To illustrate the problem, ...
0
votes
3answers
57 views

How to traverse circle coordinates?

The problem I have is: Fill a circle by drawing one-pixel-wide horizontal lines across its inside area. My initial thought is to generate the circles' coordinates symmetrically to a vertical ...
1
vote
2answers
31 views

Maximal-Orthogonal Convex Hull (or Maximal-Rectilinear Convex Hull)

In my research, I have come across a this paper from the Computational Geometry field and I am not able to understand the concept of Maximal-Rectilinear Convex Hull of a given point set in plane. In ...
3
votes
1answer
177 views

Given 3 random points, what is the probability of these two situations involving a perpendicular bisector and distances?

Suppose we're given 3 random points $p_0=(x_0,y_0),p_1=(x_1,y_1),p_2=(x_2,y_2)$ from a two-dimensional continuous uniform distribution $\{U(a,b)\}^2$, for some $(a\in\mathbb{R})\lt (b\in\mathbb{R})$, ...
0
votes
1answer
29 views

Normal to a set of integer vectors

Given a set of $i$ integer vectors resting in $d$ space (with $i$ < $d$), how do you find a normal to the set of vectors while keeping all of the computations in $\mathbb{Z}$?