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.

3
votes
1answer
28 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
25 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
51 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 ...
1
vote
0answers
26 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
17 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
31 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
28 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
109 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
43 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
36 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
17 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
11 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
46 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
20 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
13 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
45 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
34 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
62 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
62 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
26 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
29 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
44 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
30 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
14 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
20 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
20 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
27 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
42 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 ...
2
votes
0answers
28 views

Tight condition making unit-disk-graphs planar

Here's a nice property about unit-disk-graphs : Suppose $V\subseteq\mathbb{R}^2$ is a finite set of points in the plane. Build the graph $G_V=(V,E)$ such that $(v,v')\in E$ iff $d(v,v')\le2$, where ...
0
votes
0answers
20 views

How to structure data and algorithm for finding three closest latitude longitudes from a set given a single latitude longitude input

My actual language I am using is JavaScript, and the data will be structured in JSON. However that should not prevent you from answering with whatever language, data solution you prefer. I have a ...
1
vote
1answer
41 views

video shape recognition in real time

I believe from common sense that video shape recognition problems (identifying shape of a moving object) is of natural interest in many real world situations. The process of identifying is understood ...
3
votes
1answer
137 views

Linear-time algorithm to check monotonicity of polygonal chain

A polygonal chain $C$ is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $C$ at most once. I want to design a linear-time algorithm to check whether ...
1
vote
1answer
49 views

What are the primal and dual planes in the context of the point-line duality?

In computational geometry, we can define a duality between points and lines. The line is the primal (or dual) object of a point, or a point is the primal (or dual) object of a line. However, the exact ...
0
votes
0answers
36 views

Bentley-Ottmann for a mixture of segment types

Is it possible to use the Bentley-Ottmann algorithm with a mixture of allowed segment types, say, line segments and arcs? The same question could be asked for Balaban's algorithm but it's gonna be ...
0
votes
0answers
27 views

Determine an $O(nlog n)$ time algorithm for maximum matching in a bipartite graph for dominating points

You are given a set A of n points in the plane, and a set B of n points in the plane. There is a bipartite graph with edges from A to B if and only if the point in B dominates the point in A for all ...
1
vote
0answers
22 views

Polygon decomposition into minimum star-shaped polygons

As the title suggests, I'm trying to implement an algorithm to decompose a polygon into the minimum number of star-shaped polygons. I've been searching for quite some time but I can't find any ...
2
votes
1answer
78 views

How to find vertices of bounded region made by intersection of lines

Suppose we have random lines made with 2 points. and point has (x,y) For example: Now when we draw a random line you will see many lines intersect with each other. This eventually gives rise to ...
3
votes
1answer
36 views

How to efficiently find line-segment intersections between two sets?

So I'm building this iterative simulation of a surface (composed of line segments) that cannot self-intersect, which means I have to check intersections at the end of a timestep. The thing is, I know, ...
1
vote
1answer
24 views

Prove Minimum AABB Construction

Assume a point set $P[n]$ with $n$ points which align in one plane in the euclidean space, so $p(x,y) \in \mathbb{R}^2$. Looking for an algorithm to construct an AABB (axis aligned bounding box) I did ...
1
vote
1answer
60 views

How do I visit all edges incident to a vertex in a DCEL data structure?

In a doubly-connected edge list (DCEL) data structure, each vertex v stores a pointer to one arbitrary half-edge, v.inc, which ...
0
votes
0answers
17 views

Algorithm steps or Matlab Code to Create Mixture Design

Can you please put code or algorithm steps to create mixture design or space filling design. Also, what are alternative approaches to mixture design.
3
votes
1answer
92 views

Find smallest enclosing circle

On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known ...
2
votes
2answers
51 views

How to decompose a unit cube into tetrahedra?

I was presented with the problem of breaking the unit cube $[0,1] \times [0,1] \times [0,1] $ into tetrahedron shapes. The first two pieces are easy, but it's not so easy to visualize after that. I ...
1
vote
0answers
49 views

How to define the partial or total order of the segments to be inserted in a “sweep-line status” data structure?

I am interested in the details of the implementation of the "sweep-line status" data structure, which is used to implement the Bentley-Ottmann algorithm to find all intersections (and the ...
2
votes
1answer
47 views

Is it possible to transfer a point from one camera to another, given n corresponding points?

I have 2 images of a scene taken at one moment by two identical cameras (similar cameras intrinsic parameters) by to arbitrary locations and at two arbitrary orientations (different cameras poses). On ...
8
votes
2answers
134 views

How to efficiently compute the most isolated point?

Given a finite set $S$ of points in $\mathbb R^d$, how can we efficiently compute a "most isolated point" $x\in S$? We define a "most isolated point" $x$ by $$x = \arg\max_{p \in S} \min_{q \in S \...
1
vote
1answer
74 views

How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?

I am learning Shamos's rotating calipers algorithm for finding the diameter of a convex polygon in his Ph.D. thesis; Page 78. It reads Consult Figure 3.23 and notice that parallel lines of support ...