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 ...
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
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
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
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
2
votes
1answer
95 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
22 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
38 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
25 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 ...
1
vote
1answer
28 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
13 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
77 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
19 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
24 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
30 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?
0
votes
0answers
38 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
19 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
59 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 ...
2
votes
1answer
58 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 ...