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

2
votes
1answer
113 views

Maximum Side of a Square Dissected into Rectangles

Suppose a $m \times m$ square can be dissected into $7$ rectangles such that no two rectangles have a common interior point and the side lengths of the rectangles form the set ...
0
votes
0answers
18 views

Distance Geometry Problem (DGP) Programming Language Recommendation

We have been studying DGPs in clinic recently and I was hoping I might be able to get recommendations for computing languages in the processing of large network solutions. Specific computations ...
4
votes
1answer
386 views

Points in general position

I'm really confused by the definition of general position at wikipedia. I understand that the set of points/vectors in $\mathbb R^d$ is in general position iff every $(d+1)$ points are not in any ...
2
votes
0answers
22 views

Bound on “width” of points in a plane

Suppose we define width $w(P)$ of point set $P$ in a plane to be the ratio of the maximum distance to the minimum distance between the points in $P$. (Assume unique coordinates so that $w(p)$ is ...
19
votes
6answers
2k 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 ...
0
votes
0answers
14 views

Computing the approximate area of an iso surface

I'm searching for an approximation to the surface area of isosurfaces. They are defined by a constant value v in a scalar field. The scalar field is defined by placing n vectors in k-space such that ...
2
votes
1answer
78 views

Does a convex hull solution in 3 dimensions result in a minimum-area or maximum-volume solution?

The wikipedia entry for convex hull shows a 2-d example of a random set of points on x-y plane, and the "elastic band" solution that bounds the points with the convex hull solution. The definition of ...
2
votes
1answer
20 views

Largest Convex Region in a Star?

Suppose I have a star-shaped region in the plane with a particular point marked. The marked vertex is in the kernel of the star. In the image the left most point is marked in blue. Yes I drew this ...
0
votes
1answer
28 views

Computing the approximate or exact area of an isosurface

The isosurfaces I'm reading about are defined by a constant value v in a scalar field. The scalar field is defined by placing n vectors in k-space such that ...
0
votes
0answers
8 views

3D mesh segmentation simple algorithm

I am developing the algorithm reported in this article: Lest square conformal mapping Here is presented an algorithm to flat a 3d mesh on the parametric space, but i don't understand the ...
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
0answers
20 views

Subdivisions and Triangulations of Polytopes

Using one of the algorithms proposed in the chapter, triangulate the set P = P1/P2, where P1 is a hexagon given by vertices f(2; 0); (1; 2); (􀀀1; 2); (􀀀2; 0); (􀀀1;􀀀2); (1;􀀀2), and P2 is a square ...
0
votes
1answer
22 views

Polygon Equal Edge Offsetting?

If I have a random polygon of any complexity, be it a square or an irregular 20 sided polygon, how can I scale this up? I know the coordinates of each point on the polygon, but that is all. Another ...
0
votes
0answers
12 views

Proof for non-tetrahydralizability of Schonhardt polyhedron

It is established that not all polyhedrons are tetrahydralizable. Schonhardt's polyhedron is the simplest example for it. I was reading the proof for this given in the book "Art Gallery Theorems and ...
2
votes
2answers
71 views

Reliable test for intersection of two Bezier curves

Is there a test which reliably decides whether two Bezier curves intersect or not? I don't need to know how many intersections there are or at what parameters they appear at. I just would like to ...
0
votes
0answers
13 views

Intersection Multiplicity of Rational Plane Curves

Suppose I have two rational curves in the complex projective plane. I know their parametrizations, $<x_1(t),y_1(t)>$ and $<x_2(t),y_2(t)>$ I know I can use Grobner bases to find an ...
0
votes
0answers
15 views

C /matlab/ Algorithm for monotonicity of Ploygon

is there any easy and understand able algorithm to check the monotonicity of random polygon and also help me to code in which language(c or matlab) is beneficial to code the algorithm
0
votes
1answer
28 views

What is the monotonicity of a polygon? [closed]

What is the monotonicity of a polygon and why is it necessary to check the monotonicity?
2
votes
0answers
41 views

Geometric Median and Voronoi Diagrams

Is there a relationship between Voronoi Diagrams and the geometric median? I know that it is impossible to find a closed expression for the geometric median, but the two concepts seem related.
0
votes
0answers
31 views

Bearing to X,Y, Z [closed]

I’m working on a small project where I’m testing the ability of a laser to accurately measure the angle of a wire. My control for the experiment gives me X,Y,Z coordinates for a point on the wire and ...
0
votes
0answers
12 views

Most efficient way of transforming from V-representation to H-representation

What is an efficient way to transform from the v-representation of a convex hull (in terms of vertices) to its h-representation ($Ax \leq b$)?
0
votes
1answer
46 views

transforming data from cartesian plane to isometric plane

Here is a brief description of what I'm trying to accomplish. I created a 2d top down game that operated on a Cartesian plane and used some custom polygons to determine collisions and perform actions ...
5
votes
0answers
52 views

Reconstruct polyhedron from sections

There is a convex polyhedron $P \subset \mathbb{R}^{3}$ and there are its planar sections $S_{1}, \ldots, S_{n}$ througth planes $\pi_{1}, \ldots, \pi_{n}$, $S_{i} \subset \pi_{i}$. All these $S_{i}$ ...
0
votes
1answer
51 views

How do I place two points on two axis-aligned line segments such that they have given Euclidean distance l?

This is my problem: I am given two axis aligned line segments $l_1$ and $l_2$ of finite length and a distance $l$. How do I find points $p_1 \in l_1$ and $p_2 \in l_2$, such that $||p_1-p_2||_2 = l$? ...
2
votes
1answer
32 views

Bisecting points on a circle

I was working on the following problem. Given n points on a circle, where a point can be specified by its angle from the vertical, how does one find a diameter of the circle such that the number of ...
12
votes
2answers
207 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 ...
111
votes
22answers
48k 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?
1
vote
1answer
36 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 ...
8
votes
0answers
54 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 ...
4
votes
2answers
2k 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 ...
1
vote
0answers
32 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
2answers
46 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 ...
1
vote
3answers
31 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\}$. ...
2
votes
2answers
41 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
61 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 ...
1
vote
1answer
14 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 ...
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$ ...
0
votes
0answers
42 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
1answer
17 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 ...
6
votes
0answers
206 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 ...
0
votes
0answers
12 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 ...
3
votes
3answers
87 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 ...
2
votes
0answers
28 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
7 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
20 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
19 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
45 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
18 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 ...