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
1answer
31 views

Voronoi edges example

I have 4 line segments: 0 0 2 0 // 1st line segment 2 0 2 1 // 2nd line segment 2 1 0 1 0 1 0 0 and I wrote some CGAL code to print the Voronoi edges. However, ...
-1
votes
0answers
30 views

Need tools for this jigsaw-like problem [on hold]

I would like to find a tool for this jigsaw-like problem. This one is to generate all possible planar graphs under some conditions on face labels/colors. As shown in the figure, there are 11 patterns ...
0
votes
0answers
17 views

Finding the number of integer points inside a sphere of radius R and dimension D centered at the Origin

I am writing a computer program to count the number of integer points inside a sphere of radius R and Dimension D centered at the origin. In essence, if we have a sphere of dimension 2 (circle) and ...
0
votes
0answers
16 views

Similarity measure for uncertain point sets

Imagine that we have two sets of points $M=(x_{1}, x_{2},...x_m)$ and $N=(x_{1}, x_{2},...x_n)$. These are actually lists of $x$, $y$ (and $z$) in 2D (or 3D) space so $x_i\in\ \mathbb{R}^2$ (or ...
1
vote
0answers
19 views

computing the heat kernel for small times

The heat kernel on a two-dimensional manifold $M$ has the well-known expression $$H(p,q,t) = \sum_{i=1}^\infty e^{\lambda_i t}\phi_i(p)\phi_i(q)$$ where $\phi_i, \lambda_i$ are the eigenfunctions and ...
0
votes
0answers
27 views

Query about hyperplane in SVM

I am a beginner in Machine Learning. I was reading through basics of SVM and read this definition: The goal of a support vector machine is to find the optimal separating hyperplane which ...
2
votes
1answer
65 views

Area of Convex hull

For every point set $A \subset R^2$, prove that in general the sum of the coordinates of $\phi(T)$ is independent of a triangulation T and is associated to the area of the Convexv_Hull(A). We ...
1
vote
0answers
23 views

Is there an equation/algorithm to find the axis of a curved helix with varying pitch and radius?

I'm trying to find a way to numerically extract or estimate the axis of rotation for an arbitrarily shaped helix, which may be curved and have varying pitch and radius. (See here for an example.) ...
1
vote
1answer
14 views

Given a ray and line segment, compute radius of smallest circle satisfying certain criteria

Given a ray and a line segment, (efficiently) compute the radius of the smallest circle satisfying the following criteria: The circle contains the origin of the ray. The center of the circle lies on ...
0
votes
0answers
19 views

Rotate circle about line if a point on circle is on the line

I'm working with unit-distance graphs in $\mathbb{R}^3$, so all points are in $\mathbb{R}^3$ and points $x$ and $y$ are adjacent (notation: $x \sim y$) if and only if $|x-y|=1$ (where $|x-y|$ denotes ...
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
46 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
19 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
22 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
7 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
24 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
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
16 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
248 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
303 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
19 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
15 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
88 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
54 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
422 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
24 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
18 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
55 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
148 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
28 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 ...
118
votes
22answers
53k 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
16 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
41 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
49 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
37 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 ...