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

0
votes
0answers
14 views

Find 2 point getting far away each other from their intersection point

I want to know how to find 2 aircraft getting far away from their intersection point, from Dataset such as aircraft 6-7,11-2, 10-6,37-36,etc. Dataset: my algorithm is: calculate direction ...
11
votes
2answers
11k views

Point closest to a set four of lines in 3D

Given four lines in $3D$ (represented as a couple of points), I want to find the point in space which minimizes the sum of distances between this point and every line. I'm trying to find a way to ...
1
vote
0answers
42 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than $2$ I should choose a special partitioning hyperplane for the divide and conquer algorithm to get $O(n \log n)$. I am confused because to choose this ...
0
votes
1answer
18 views

Show that the intersection between a polygon and convex hull can be computed in the O(n+m)

I am trying to understand triangulation, explained in the book "Computational Geometry Algorithms and Applications, 3rd Ed - de Berg et al". Unfortunately, I don't know how to solve the following ...
0
votes
0answers
20 views

Shatter coefficient and VC dimension of a grid in $R^d$

Given $\epsilon>0$, partition the cube $[0, 1]^d$ with square of side length $\epsilon$. The total number of square in the partition is $$ N = \left(\frac{1}{\epsilon}\right)^d. $$ What is the ...
0
votes
0answers
6 views

Given M points and a weighted graph G, map the vertices to distinct points to minimize sum(edge_weight*edge_length)

Given an arbitrary undirected weighted graph G with N vertices, and an arbitrary set of M points P in euclidean 3-space, where M>=N, map the vertices to distinct points such that sum(edge_weight * ...
0
votes
0answers
6 views

K-Server Problem on a Unit Square

How does a K-Server clustering look on the set of all points on the unit square? It clearly must be equal to a Voronoi diagram almost everywhere, but what is the configuration of cluster centers and ...
0
votes
0answers
21 views

Rectangle-Rectangle Intersection Area - Area Only

Suppose I have two rectangles that are not necessarily axis-aligned. What is a fast way to calculate their intersection area? Note that I am aware of convex polygon intersection and area algorithms; ...
0
votes
0answers
7 views

Optimal locations for vertices of a polygon with given area

I want to find the optimal locations for vertices of a polygon (with area A) such that it is as close as possible to the desired area A'. Please note that the vertices need not be fixed at their ...
0
votes
0answers
5 views

Bottleneck Distance Significance?

Let $X$ be a smooth manifold and $f,g:X\rightarrow \mathbb{R}$ two real valued functions on $X$. Suppose we have two persistence diagrams $Dgm(f)$ and $Dgm(g)$ encoding the lifetime of $k$-dimensional ...
0
votes
0answers
14 views

What is bottleneck distance intuitively?

Can someone explain the intuition behind Bottlneck and Wasserstein distance? The context here is the comparison of two persistence diagrams.
1
vote
1answer
241 views

Determining if a set of hexagons on a grid can tile the plane

Suppose I have a regular grid of identical hexagons that tile the plane, that is a hexagonal lattice. How can I determine if a connected subset of these hexagons (i.e. a poly-hex) can tile the plane ...
9
votes
1answer
299 views

Optimal bounding boxes selection for $N$ rectangles

Suppose that I have $n$ straight rectangles on a plane $r_i = (x_i,y_i,w_i,h_i)$. Each rectangle has a cost function, its area $A(r_i) = w_i \cdot h_i $. I can also "merge" 2 or more rectangles into ...
1
vote
0answers
24 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
3
votes
0answers
162 views

How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?

I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...
1
vote
0answers
18 views

create polygon section with equal sides

I have to create essentially these sections of a polygon. I have width(W) and height (H), and number of sides (3 on left abc and 4 on right image ABCD) I need each side to be equal. How can I ...
0
votes
0answers
40 views

Finding the vertices of a square giving the mid point and radius

I'm a programmer with terrible mathematics skills, but I'm getting by with studies. I'm trying to find out the vertices (x,y) of a square, giving the ...
0
votes
1answer
13 views

Representing results of CSG operations with spline-based surfaces

I've been playing with a few different CAD programs and have become interested in the math involed with CSG and spline-based surfaces. During my research, I found that the curve representing the ...
1
vote
2answers
79 views

NURBS Curves to Interpolate Points and Derivatives on a Surface of Revolution

Problem in Prose My starting point is a set of conic segments on a plane. Each of these conic segments interpolates between three points and known slopes on the two outer points. I want to find a ...
3
votes
2answers
51 views

Largest four line segments of polygon

I have some polygon (see darkblue contour): It consists of very small segments, pixel by pixel, so angles differ although they seem to be the same. Visually we see 4 large line segments. How can I ...
0
votes
1answer
30 views

On applications of Alexander's Theorem

I would like to know a bit about applications of the Alexander Theorem from Knot and Braid Theory. I would be very interested in learning about possible applications for the description of everyday ...
1
vote
2answers
35 views

Given a band of $m$ opaque squares arranged in a circle, can we find a viewpoint from which we see exactly $m/2-1$ squares?

Given a band of $m\ge 3$ opaque squares arranged in a circle, can we find a viewpoint (i.e. a point on a sphere centered at the midpoint of the circle with a radius large enough to see the whole ...
4
votes
1answer
411 views

Poisson point process (PPP) and Voronoi cells

Say we have a homogeneous PPP with rate $\lambda$ in the 2-D plane $\mathbb R^2$. In one realization of the PPP we get the points $\phi=\{x_1,x_2,...,x_i,...\}$. Now we generate the Voronoi cells ...
0
votes
1answer
23 views

Minkowski sum and Polygons

The problem:.. Given two convex polygons $A$ and $B$, we can define Minkowski sum as A + B = {a + b: a $\in$ A, b $\in$ B}, where $a + b$ vector sum. Prove that: every vertex $p \in A + B$ is a ...
0
votes
0answers
17 views

Visible faces of a polyhedron $P$ on a path of viewpoints on the unit sphere looking at the center of $P$

Let $P$ be an opaque polyhedron. Assuming parallel projection, let's define a viewpoint to be a point on the unit sphere around the center of $P$. Let's say that two viewpoints $v_1$ and $v_2$ are ...
1
vote
1answer
24 views

Prove that for any n > 3 there is a set of n point sites in the plane such that one of the cells of Voronoi diagram(P) has n − 1 vertices

I am trying to solve some exercises of the book "Computational Geometry Algorithm and Applications, 3rd - de berg et al" of chapter 7 - Voronoi Diagrams. Unfortunately, I am not sure if I understand ...
1
vote
1answer
54 views

Minkowski sum and vectors

Problem: Given two convex polygons A, B, we can define Minkowski sum, as A + B = {a + b: a $\in$ A, b $\in$ B}, where a + b vector sum. Prove that: for every external perpendicular u to an edge of ...
3
votes
1answer
144 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 ...
8
votes
5answers
6k 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 ...
0
votes
1answer
29 views

Number of fragments into which a fixed triangle is cut in the 3d version of the binary space partitioning algorithm

You can scroll down the question, if you're familiar with the construction of a 3d binary space partition as presented in the book Computational Geometry: Algorithms and Applications by Mark de Berg ...
1
vote
1answer
22 views

Why is no analysis possible for the 3d version of the random binary space partioning algorithm?

Let $S$ be a set of $n$ non-overlapping line segments in the plane $\ell(s)$ be the line which contains $s\in S$ $\ell^+$ and $\ell^-$ be the half-plane above and below of a line $\ell$, ...
1
vote
1answer
47 views

Why do at least half of all random orderings generate a binary space partition of size $n+4n\ln n$ in the random binary space partition algorithm?

Let $S$ be a finite ordered set of non-intersecting finite line segments in the plane. Let's randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal ...
0
votes
1answer
43 views

Expected number of fragments generated by a random binary space partition (should be plain combinatorics)

Let $S$ be a finite ordered set of non-intersecting finite line segments in the plane. Let's randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal ...
3
votes
1answer
40 views

Simplifying polygons

I want to turn digitized polygons into simpler shapes. More precisely, given a noisy closed polyline, I want to fit a polygon to it with an imposed number of sides, such as a triangle or ...
0
votes
1answer
24 views

Correctness of the sweep line algorithm for line segment intersection in the plane

Suppose we are given a finite set $S$ of line segments in the plane and the intersection between two segments is empty or a single point in the interior of both segments at most two segments ...
117
votes
22answers
52k 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?
0
votes
0answers
15 views

finding equation of a planes of frustum

i have a frustum and i have 4 components for each plane of a frustum, first 3 components stands for a normal to that plane and last component is its distance from the origin. I have another frustum of ...
0
votes
1answer
37 views

find coordinates of point of intersection of 3 planes

i have normal to a plane and its distance from origin i.e. 4 components for each plane. if i have given 3 such planes and know that they are intersecting at a single point. how do i calculate ...
0
votes
0answers
18 views

Minimum bounding rectangle is aligned with the convex hull

To start off, here's the problem I'm trying to solve: Suppose we have a finite collection of points in 2D. We would like to find the minimal bounding rectangle (MBR) for these points. By definition, ...
3
votes
0answers
47 views

Centroid and circumcenter — how close?

Suppose $R$ is some planar region, bounded by a curve. Let $C_1$ be the centroid of $R$, and let $C_2$ be the center of the "circumcircle" (the smallest circle enclosing $R$). Intuitively, it seems ...
0
votes
2answers
36 views

Finding the boundary of a triangle given the area

This post is math related but my concerns include the correct algorithm I can use in a program. I have been advised to post here as well as on stackoverflow, so maybe I can get some math related ...
3
votes
0answers
53 views

convex polygon triangulation

Suppose we have given a convex polygon on $n$ vertices $P= \{ a_1, \cdots , a_n \}$ in the plane (arranged clockwise). How can we prove that there exist atleast two indices $i$ such that circle ...
2
votes
0answers
15 views

Tracing the faces of a convex polyhedron from edges and vertices

I have a set of vertices and edges that by construction, form a convex polyhedron. I would like to know how to trace out the faces of such a polyhedron i.e. find a list comprised of set of edges that ...
2
votes
0answers
47 views

Polyhedra from number fields

A question on the disnub mentions golden ($x^2-x-1=0$) gives the dodecahedron + much more. tribonacci ($x^3-x^2-x-1=0$) gives the snub cube. plastic ($x^3-x-1=0$) gives the snub ...
2
votes
2answers
34 views

Could tertiary computation negate the need for large memory?

In normal computers, pointers in code "point" to memory. On a lower level, linking and loading turns those "pointers" into numerical codes which really do point to specific bytes (or bits) of ...
2
votes
1answer
727 views

How can I define a measure of similarity between two line segments in $\mathbb{R}^2$?

I have two segments in $\mathbb{R}^2$ and I would like to define a measure of similarity between the two segments. My idea is that I can apply: a scale transformation $s$ in order to equate the ...
1
vote
2answers
2k views

Polarity of the Surface Normal of a 3D triangle

I have a triangle (defined in 3D space) that has 3 points (p1, p2 and p3). Is it possible to work out what the polarity of the surface normal would be for the face knowing it lists each point in an ...
0
votes
0answers
26 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
476 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
25 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 ...