Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions about algorithmic solutions of geometric problems, or other algorithms making usage of geometry.

1
vote
1answer
11 views

Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices

I'm trying to minimize the area of a simple (non-intersecting, without holes) polygon by adding points to it, or modifying points of its subset. Let me describe this more formally: Let: $P$ be a ...
1
vote
0answers
18 views

Removing fish-eye effect

The DNG specification (page 87) describes a simple algorithm for converting a "fish-eye" photo into a regular photo (just several lines of basic geometry). The transformation is configured using six ...
0
votes
0answers
9 views

Hit-and-run stucks near edge/corner of polytope

I try to generate random points within a convex polytope. Hit-and-run sampling can get stuck near the edge and corner of a polytope if I use a moderate number of steps. A point at the corner has ...
1
vote
1answer
16 views

How to check if a given point is inside a polygon with holes?

How to check if a given point lies inside or outside a polygon with holes? Does the below algorithm works for polygon with holes? https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-...
3
votes
1answer
30 views

Concave Polygon Intersection - Algorithm

I'm trying to develop an Algorithm for Polygon Intersection. Where each polygon is an array of Points, where each Point has X and Y properties. Algorithm limitations: - Algorithm input: 2 Polygons. - ...
0
votes
0answers
16 views

Geometric algorithm which solve a cluster problem for high-dimensional data

Since I'm new in using geometric algorithms for machine learning, I hope to get help here. I'm looking for a topic for my thesis that deals with algorithms that solve cluster problems in high-...
2
votes
1answer
42 views

Making a profit as a high-dimensional store owner?

Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient. Let's say that I am some business owner with a set of $...
0
votes
0answers
35 views

Computational geometry in machine learning

So far, I have thought that an algorithm that solves a cluster problem, can be assigned to unsupervised learning, because clustering is part of machine learning. If I have now given an algorithm ...
3
votes
2answers
73 views

Uniform sampling over non-standard simplex

Uniform sampling over a $n$-dimensional standard simplex is described here: Uniform sampling from a simplex I want to sample one point from a non-standard simplex with vertices at: $s_{i}\vec{e_{i}}$...
1
vote
1answer
35 views

Randomly choose vector b in range such that $\vec{a} \cdot \vec{b} = 1$

Given I have a $n$ dimensional $\vec{a}$. All elements of $\vec{a}$ are between 0 and a positive number $K$. $n$ is about 15 to 20. Problem I want to randomly and unbiasedly choose a vector $\vec{b}...
1
vote
0answers
28 views

Check if no linear combination is within a hypercube

Shapes Let $C$ be the unit hypercube in $\mathbb{R}^{n}$. Let $\vec{o}$ be a point in $\mathbb{R}^{n}$. Let $B$ be a $n \times m$ matrix. The columns of $B$ are a set of linearly independent vectors ...
0
votes
0answers
12 views

What is the advantages of decision diagram over decision tree?

while reading few articles I come across few doubts. Could anyone please help me ? The below mentioned are the questions 1)What is the advantage of Decision Diagram over Decision Tree? 2)Is Decision ...
0
votes
0answers
12 views

angle constraint on convex hull

Given a set of points $P$ in $R^d$ it is straightforward to compute the convex hull (Graham-scan etc). However, the angle between the adjacent faces are unconstrained (apart from necessitating that ...
0
votes
0answers
7 views

volume of convex hull given boundary

Suppose we are given a boundary $ \Gamma \in R^3$ (the boundary not necessarily being convex) and asked to estimate the volume of the convex hull, can we do so without actually computing the convex ...
2
votes
2answers
71 views

Is there an algorithm to find all vertices that are inside of a shape?

In computational geometry, is there any algorithm to find all vertices that are inside of a shape? All vertices of graph has $x$- and $y$-coordinates Shape is a set of points with $x$- and $y$-...
1
vote
1answer
32 views

Robot swarm, Maximum area coverage

I have a swarm ofN robots to place on a plane area. Each robot would control a sub part of the area (navigating in it). What algorithm could I use to deploy my ...
1
vote
0answers
61 views

Similar to point location

I have a following problem: Given a set $S$ consisting $N$ triangles (possibly overlapping). Answer queries (online) of the form: given a point $P$ is there a triangle $T$ in $S$, such that $P$ lies ...
1
vote
1answer
44 views

What is the relation between Computer Graphics, Discrete Geometry, and Complexity Theory?

I am a master computer science student, and I am interested in both geometry and complexity theory. So I would like to know what is the relations between discrete geometry, computer graphics, and ...
1
vote
0answers
35 views

Connect cylinders with a sphere in 3D

I'm trying to connect cylinders with a sphere in 3D smoothly. The sphere is given by a single 3d point-diameter data and the cylinders are given by point-diameter data as well for the start of the ...
3
votes
1answer
29 views

How would I algorithmically “stretch” polygons on a plane by re-scaling the distances between interior points?

I've been thinking about a computational problem and could use some guidance for how to go about developing an algorithm to solve it. On a Euclidean plane, I have a polygon A, a set of points A* ...
0
votes
2answers
26 views

Can area-partitioning lose included points due to floating point precision?

I'm currently partitioning a big area $A$ into $n$ areas $B_i$ such that $$\bigcup_{i=1}^n B_i = A$$ I have geo-coordinates which I know are in $A$ (also with the finite precision of floats). ...
3
votes
1answer
65 views

Is binary-search really required in Chan's convex hull algorithm?

I have a little doubt about Chan's algorithm. From Wikipedia's description we see that the second phase of an algorithm works with $K = \mathrm{ceil}(\frac{n}{m})$ subsets $Q_i$. The goal of the ...
4
votes
0answers
85 views

One-sided, distance-optimal polyline reduction to a given number of vertices

So I have been battling this rather peculiar problem: given the following input (on an euclidean plane): point p polyline l integer n p is not inside of the convex hull of l find a new polyline l', ...
0
votes
0answers
18 views

Are point clouds faster to render than triangle meshes? What are the advantages of using one over the other?

I searched online but I couldn't find any comparison between rendering a point cloud and rendering a triangle mesh.
2
votes
1answer
71 views

Minimum distance between two convex hulls maximized

I want to implement a program that splits a set $S$ of $n$ points in the plane into two sets such that the distance of the convex hulls of the two sets is maximized. It should be done in $O(n^3)$. I ...
1
vote
0answers
30 views

What areas of geometry are used in computer graphics?

I've taken intro to graphics and am interested in diving deeper into the subject. My understanding is that the field depends a lot on geometry, but I'm having trouble figuring out exactly what ...
7
votes
1answer
121 views

Find a straight line to divide two convex polygons by equal area

Suppose, we have two non-overlapping convex polygons $A$ and $B$. How can we draw one straight line which divides $A$ into two parts of equal area and also divides $B$ into two equal area parts? Also, ...
3
votes
1answer
45 views

Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
1
vote
1answer
44 views

Shifting positive values in an array to offset the negative ones, in less than O(n^3)

I have an array 'a' which is 1xn, and has positive and negative values. In a rolling window of size m smaller than n. I want to move backwards (to the left) the positive values of the array in order ...
1
vote
1answer
25 views

Find an edge that is completely visible from point outside a polygon (Convex Hull)

I want to implement algorithms from this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.5609&rep=rep1&type=pdf In particular, I am currently dealing with the one in ...
0
votes
0answers
12 views

2 monotone chains intersection detection: How to find which part of chains to exclude

While checking if 2 monotone chains intersect with each other we need to check if their median edges intersect. If they don't, we exclude some parts of the chains and continue from there. So how do we ...
3
votes
1answer
48 views

Why is the graph inside Graham Scan always planar

One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's ...
0
votes
1answer
21 views

Formal definition of loss surface of multi-layered networks

Let $\mathcal{L}$ be a loss function associated with a multi-layered neural network. So it seems almost everyone in AI/ML community is interested in the Hessian $H=\partial^2 \mathcal{L}$ of $\...
0
votes
0answers
14 views

Reward surface in reinforcement learning

There is a remarkable paper [1] which explores geometry of neural network. I believe this information is quite helpful in plethora of optimization methods. In reinforcement learning, the optimization ...
4
votes
0answers
48 views

Partitioning rectangles

Suppose that there are rectangles in the Cartesian plane, each aligned with the axes---the rectangles are defined by left and right x-coordinates and top and bottom y-coordinates. There are two ...
1
vote
1answer
35 views

Find coverage for plane from half-planes

The document (see pic. below) states that it is possible to find a cover of the plane by a subset of 3 half-planes. It proposes to use linear programming for this. How to formulate such a program? ...
1
vote
2answers
63 views

How can two maps be compared?

The scenario is the creation of street maps. For example, two people at Open Street map edit the same part of the map at the same time. Now the one that submits the data later should see a diff. ...
2
votes
1answer
74 views

Can we easily check if we can place two not-intersecting circles inside a convex polygon

We have given convex polygon of $N$ vertices, and two circles of radius $r$. Is it possible to check if we can place those two circles completely inside the polygon, such that they don't intersect, ...
3
votes
0answers
29 views

Art Gallery Problem in 3D

Basically, I'm interested in doing 2 things. Let's say we have a mesh M. 1. Find the minimum number of points(inside M) required to see the whole M. 2. Decompose M into polyhedrons which can be ...
0
votes
1answer
37 views

Minimum square side length to enclose n circles of radius r

I thought of a problem but have no idea how to solve it. The problem is as follows: Given 2 numbers, n and r, find the side length (S) of the smallest square that encloses n circles each of radius r ...
2
votes
0answers
24 views

Maximum boundary edges amount of union of rectangles

I've read that the maximum boundary edges amount of union of $n$ rectangles, named $p$, is bounded by $p \leq n^2 + 4n$ I tried to prove this by induction, but it's seems too difficult to me, can ...
2
votes
1answer
49 views

Algorithm for nearest edge detection with respect to a point (in all directions)

I'm looking for an algorithm, a set of algorithms, or any pointers/remarks how to solve the following problem: Given a polygon, a central point, and a set of points scaterred around the central point ...
1
vote
0answers
31 views

Exact cover with cover size known

I know that the exact cover problem has a pseudopolynomial algorithm when the cover size is a given constant (as here: Is set cover still NP-complete if you have a given k?). However, I am interested ...
0
votes
0answers
14 views

Downsides of using convex layers for listing and counting points inside a triangle

Given a set of points S and a triangle, what are the various reasons for which constructing and using the convex layers of S is not optimal for counting and listing the points inside the triangle?
1
vote
0answers
15 views

Counting Number of Points Satisfying given Equation

I am given set of points S. I need to find the count of four vertices (A, B, C, D) satsfying the equation AB + CD = BC + AD, morever, the vertices should be pairwise distinct. Here, A, B, C, D ...
1
vote
0answers
23 views

Algorithm to merge multiple polylines into contours

There is a set of 2D polylines, each polyline defined by an ordered array of vertices (each vertex is joined with the previous one by a line, if drawn). Together, when drawn, these polylines form one ...
1
vote
1answer
24 views

If $V$, $E$ and $F$ is respectively the number of vertices, edges and faces in a maximally triangulated graph, then why do we have $3F = 2E$?

Suppose we have a maximally triangulated graph $G$, where $V$, $E$ and $F$ is respectively the number of vertices, edges and faces. The following graph should be a maximally triangulated graph. ...
0
votes
0answers
30 views

What is the actual complexity of this algorithm?

I am reading O'Rouke's Computational Geometry in C and I am not sure whether the complexity of this algorithm is correct. First there is a verbal description "Find a diagonal, cut the polygon into ...
1
vote
0answers
23 views

converting a triangulated surface to min-max form

Let $S$ is a triangulated surface, representing a graph of a function z(x,y) in 3D space. According to https://en.m.wikipedia.org/wiki/Piecewise_linear_function every continuous piecewise linear ...
3
votes
1answer
54 views

Solving a variant of the Exact cover problem

I am trying to solve a variant of the Exact cover problem where every element has to be covered exactly twice instead of once ( i.e. has to be in exactly two sets that are part of the cover). Now, it ...