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 tagged [computational-geometry]

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

15
votes
2answers
2k views

What is this data structure/concept where a plot of points defines a partition to a space

I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem. Basically it's a plot of points, and the ...
1
vote
0answers
34 views

An efficient algorithm to find a linear transformation between two ternary quadratic forms

Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms $$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\ Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$ over the field $\mathbb{F}...
2
votes
0answers
37 views

Find points that lie outside of a series of triangles

Suppose there are $n$ triangles on a 2D plane, which don't cross each other and have no common vertex. Suggest an algorithm that gets $n$ points and in $O(n \log n)$ determines the points that don't ...
3
votes
1answer
53 views

Prove that there always exists a line bisecting each of two point sets

A line $\ell$ for a set $S$ of points is bisecting if the open halfspaces on either side of $\ell$ contain at most $\frac{|S|}{2}$ points. Now given point sets $A$ and $B$ in the plane, prove that we ...
2
votes
1answer
13 views

Determine Intersection given only a hyperrectangle and a point-contained-in-shape-Predicate

Given only an n-dimensional hyperrectangle by its corner-point-values and an n-dimensional Predicate that corresponds to an arbitrary shape and tests whether a point is contained in said shape, is it ...
3
votes
2answers
239 views

Bucket computation, cutting array with lines

Given an NxN array, drawing a line from the edge's midpoint to the opposite field how can the N buckets be found covering the majority of the line's path? A visual aid: Is there a better way to ...
0
votes
1answer
23 views

How to find the angle of an arc to draw graphic

I would like to draw an arc from a specific point to a goal point, during the process of drawing a larger path. I would like to do it using bezier curves, which aren't adequate for modeling circular ...
2
votes
1answer
30 views

Convert NURBS curve into Cubic Bezier Curve

From this: Maybe you already know this, but it's impossible to convert nurbs to bezier splines exactly because nurbs are rational functions, and bezier splines are polynomials. I don't understand ...
2
votes
1answer
72 views

Can I compute closest split pair of points where distance is strictly less than delta

I've been studying the closest pair algorithm lately and I found this to be an extremely good and intuitive resource: http://serverbob.3x.ro/IA/DDU0221.html. It is also explained in section 33.4, "...
1
vote
1answer
36 views

Real RAM computational mode

Given a real value $M>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number ...
0
votes
0answers
9 views

Lower envelope surface for 3d surfaces

Are there any fast algorithms for computing the lower envelope surface for a parametric family of surfaces $f_{a,b}(x,y) = \frac{a-x}{b-y} + c$, where (a,b,c) are parameters.
0
votes
1answer
26 views

Point rank in 2D plane time complexity?

I'm reading about the algorithm of finding the ranks of all points in a 2D plane, I don't understand the time complexity formula for it. It has four steps: Compute the median of x-coordinates of all ...
1
vote
0answers
16 views

Transform Image Point to Azimuth and Elevation

I'm working on an object tracker where I need to report the azimuth and elevation of targets. Both values should be scaled from degrees to unsigned 32-bit integers. For now I can ignore lens ...
0
votes
0answers
31 views

Randomly choose matrices $A_{j}B = C_{j}$ with elements between 0 and 1

Problem I have $J$ matrices $C_{j}$, which are $K \times M$. Elements of each matrix $C_{j}$ are between 0 and 1. I want to randomly choose $J$ matrices $A_{j}$ and one matrix $B$ such that: ...
3
votes
0answers
25 views

How to maintain completely dynamic convex hull quickly?

If there's no deletion, we can use $2$ balanced trees to maintain $2$ half convex hulls(up and down). In this way, we can insert $n$ points in $O(n\log n)$ time.(In the beginning, there are no points) ...
2
votes
2answers
76 views

Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
0
votes
0answers
16 views

Find the direction of monotone polygon (if exists) in linear time

Implement a program that checks if there is a direction in which a simple polygon is monotone and,in that case, reports such a direction. Upper bounds: O(n) time, where n is the size of the ...
2
votes
1answer
51 views

3D gift wrapping algorithm: how to find the first face in the convex hull?

I am implementing the gift wrapping algorithm to find the convex hull of a set of points in the 3D space. However, all the articles I have read seem to omit the description of the first step of the ...
2
votes
1answer
21 views

Find pair of complex numbers with maximal sum

Given two lists of complex numbers, is there an efficient algorithm to choose one element from each list such that the magnitude of their sum is maximal?
1
vote
0answers
16 views

Algorithm to compute the difference between two geometric paths

I want to compute the difference/intersection between two paths. By path I mean a list of points that can be created by the following actions on a graphics context: move to x, y line to x, y Bézier ...
1
vote
1answer
24 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
25 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
12 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
46 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
2answers
99 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. - ...
2
votes
1answer
46 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 $...
3
votes
2answers
82 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
37 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
29 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 ...
-1
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 ...
2
votes
2answers
73 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
34 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 ...
2
votes
0answers
63 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
50 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
33 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
29 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
79 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
90 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
26 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
161 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
34 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
132 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
49 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
50 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
28 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
49 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
29 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
16 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 ...