Stack Exchange Network

Stack Exchange network consists of 175 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.

0
votes
0answers
17 views

Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of N non-overlapping convex polygons {S_i, i=1..N} defined by their vertex coordinates (x,y) and a convex polygon P, also defined by its vertex coordinates, find all polygons S_i ...
1
vote
1answer
51 views

An algorithm that find the max X/Y in a polygon in O(log n)

I got a task to create two functions one finds max $X$ and the other $Y$ in a polygon in $O(\log n)$. The polygon is represented by an array of its vertices where each vertex is represented by its ...
3
votes
1answer
43 views

Global indexing of shared nodes in parallel

Consider a tiling of quadrilaterals in 2D that provide complete coverage of a particular region. N quadrilaterals are distributed across many parallel threads, typically in a way to keep groups of ...
5
votes
1answer
36 views

Partitioning connected graphs in the plane

This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes. How can we divide the plane using line segments in such a ...
4
votes
1answer
60 views

Smallest convex set containing given point

Given a set $M$ of $m$ points in $R^n$, where the number of points $m$ is much larger than the dimension $n$, and given a point $x$ in $R^n$ that we may assume is in the convex closure of $M$, is ...
6
votes
1answer
51 views

Can one count the number of n points in m triangles in less than O(nm)?

We have n points given as $(x,y)$ coordinates and m triangles given as triples of $(x,y)$ coordinates, and want to count the number of times that one of the points is inside one of the triangles. The ...
1
vote
0answers
17 views

DCEL operations on quad-edges, Twin, Next, and Prev

Suppose I have a quad-edge data-structure, and I want to be able to perform the operations of DCEL (twin, next, ...
2
votes
2answers
164 views

Minimizing the maximum Manhattan distance

Given N points on a grid, find the number of points, such that the smallest maximal Manhattan distance from these points to any point on the grid is minimized. Also, determine the distance itself. ...
0
votes
0answers
27 views

Find the smallest width annulus in O(n)

Given set of points (in the plane), find in a linear time the smallest width annulus (annulus is the region between two concentric circles) that contains all the points. Because of the time ...
4
votes
2answers
79 views

Add lines to star with fixed coordinates maximizing smallest angle

I have the following problem: There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change....
1
vote
0answers
35 views

Algorithm to determine paths that define shape of connected rectangles

Say you have a bunch of rectangles like these: They get organized into 3 distinct final shapes like this: As you can see, there are a few "complete contours", as in here: The way you figure out the ...
2
votes
2answers
69 views

Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$?

Suppose I have $n$ horizontal segments in the plane (i.e. their end points share the same $y$ value). I want to determine if there exists a line that intersects all such segments. I think I can ...
1
vote
1answer
49 views

Is there an algorithm to find the minimal number of dimensions, given the distances between points?

Given some finite set $S := \{x_1,x_2,\ldots,x_k\} \subset \mathbb R^n$ we can define a distance matrix $D = (d(i,j))_{ij}$ with $$d(i,j) = \Vert{x_i - x_j}\Vert$$ where $\Vert \cdot \Vert$ is the ...
2
votes
1answer
66 views

Longest-path in a graph, where the path should be 'straight'

Is there any existing work done on finding paths that are geometrically straight? I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of ...
4
votes
1answer
55 views

Algorithm to separate circles to reduce collision the maximum between them

I'll try to do my best to explain this. I have X circles (from 2 to 4) which can move around smaller pivot circles. The pivot circles are fixed and cannot be moved once they are in the "field". Pivot ...
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 ...
2
votes
0answers
42 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
45 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
55 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
20 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
243 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
27 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
40 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
84 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
37 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
10 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
25 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
32 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: ...
4
votes
0answers
34 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
77 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
24 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
162 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
19 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
26 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
27 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 ...
1
vote
1answer
112 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
217 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
47 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
89 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
38 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 ...
2
votes
2answers
77 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
35 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
52 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
36 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
34 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). ...