Questions tagged [computational-geometry]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
42 views

Algorithm to find the shortest path and its length for moving between many geometries

I have a set of 2D geometric figures in Cartesian space, as shown in the image. Each geometric figure has a start point and an end point (among other characteristics). For closed geometries, such as a ...
3
votes
1answer
49 views

N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100. To calculate the sum of ...
2
votes
0answers
55 views

Collision between a bi-infinite linear sequence of 2D integer lattice points and any of a fixed set of such sequences

Given: a finite collection $V$ of bi-infinite linear sequences of two-dimensional integer lattice points, each sequence ${V_i}$ given by $\vec{{V_i}_j} = \vec{{V_i}_0} + j*\vec{d_i}$. (A natural way ...
4
votes
1answer
45 views

Find the segments set with the lowest number of 2D collisions

I am given 2 sets of n 2D Points. I need to find the segment set S where each of the n segments has its start and end in the first and second set respectively. The requirement is that each point must ...
0
votes
1answer
4k views

Divide and Conquer Algorithm for Hidden Line Removal

You are given n nonvertical lines in the plane, labeled $L_1, ..., L_n$, with the $i^{th}$ line specified by the equation $y = a_i x + b_i$. We will make the assumption that no three of the lines ...
3
votes
0answers
30 views

Periodic 4D Triangulations

I am looking for references and/or algorithms for generating 4-dimensional periodic triangulations on unit 4 lattices. That is, generating a space filling triangulation of the 4D integer lattice (Z^4) ...
4
votes
1answer
97 views

Point in Polygon on the sphere

I'm looking at geometric objects on the sphere and need to determine if a point on the sphere is inside a spherical polygon. In our case a spherical polygon is a an ordered set of vertices $v_1v_2......
1
vote
1answer
42 views

Similarity measures for (geometric) triangulations

In a project I am working on, we are looking at multiple different (optimal with respect to some cost measure) triangulations of a fixed pointset $S$. I would like to cluster similar triangulations. ...
4
votes
0answers
54 views

Finding the smallest distance between a point and a set of points

I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this ...
3
votes
1answer
138 views

Can breakpoints of the beachline move up in Fortune's algorithm?

In these slides describing Fortune's algorithm for constructing a Voronoi diagram, it is noted on page 7 that break points of the beach line can move upward. How is this so? In most of the cases I ...
2
votes
0answers
52 views

Fast algorithm to check if a query line segment contains a point that is not covered by $n$ disks in $\mathbb{R}^2$

I have a list of $n$ disks in $\mathbb{R}^2$ with center and radius $(x_i, y_i, r_i)$. I also have $Q$ line segments $l_1, l_2, ..., l_Q$. I am interested in preprocessing the $n$ disks (or the line ...
1
vote
1answer
100 views

Description of shape in a vector form

I would like to ask for references to algorithms that can project shape information about an object to 1 dimension. Specifically I am training a neural network to be able to identify objects with ...
2
votes
1answer
135 views

Calculate the area of the shape created by multiple paths

I'm trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example: Basics 4 separate paths (A,B,C,D) which are a collection of ...
0
votes
1answer
31 views

Given a rectangle and a circle (having a lattice point as a center) find the number of lattice points of the rectangle inside the circle

The title explains the question easily. Also the radius of the circle is always an integer. The naive algorithm I thought was to check each and every lattice point of the rectangle but I wonder if we ...
7
votes
0answers
147 views

Finding a rainbow independent set in a circle

Inside the interval $[0,1]$, there are $n^2$ intervals of $n$ different colors: $n$ intervals of each color. The intervals of each color are pairwise-disjoint. A rainbow independent set is a set of $n$...
1
vote
1answer
109 views

Is there an algorithm to solve the following point clustering problem?

According to this post Given $n$ points $P=\{p_1,p_2,\dots,p_n\}$ in 2D space, and a matrix $D^{n\times n}$ with the distances between each pair of points, we want to partition the points into two ...
4
votes
0answers
58 views

Efficient 2d interval merging product

Suppose I have two tables of 2d intervals (axis-aligned rectangles) with values attributed to each interval. ...
2
votes
0answers
52 views

Approximation algorithm for minimal Covering of an orthogonal polyhedron

Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for ...
2
votes
0answers
17 views

Algorithm to batch individual cells into blocks based on attribute

This is a real world algorithms problem I came across while coding an application for excel. The background: In excel, we have to write color information to the sheet one cell at a time - there are no ...
1
vote
0answers
24 views

How does Bowyer-Watson algorithm for Delaunay triangulation run in $O(n^2)$ but runs over all the simplexes?

The Bowyer-Watson algorithm for Delaunay triangulation is known to run in $O(n^2)$ according to the authors, where $n$ is the number of data points in $\mathbb R^d$. In addition, the algorithm (for ...
2
votes
0answers
25 views

Best grid/lines to map a group of points

The data I have is a group of points with their position (x,y) known: It is known that all these red dots are situated exactly on the lines which form a grid system like following: My object is to ...
3
votes
1answer
794 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 ...
1
vote
1answer
274 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 | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
12
votes
3answers
4k views

Closest pair of points between two sets, in 2D

I have two sets $S,T$ of points in the 2-dimensional plane. I want to find the closest pair of points $s,t$ such that $s \in S$, $t \in T$, and the Euclidean distance between $s,t$ is as small as ...
3
votes
0answers
111 views

Seemingly simple path finding problem, but graph with travelling salesman or shortest path does not work

I am looking for an algorithm to a problem that I encountered when working with 3D modeling: On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on ...
1
vote
0answers
9 views

Methods to interpolate between 2 topologically identical 3D meshes

I have 2 3D surface meshes. These meshes have vertex-correspondence and have the same topology (same edges and triangles connecting the vertices). However, the vertex positions (3d coordinates) are ...
3
votes
0answers
21 views

Dynamically compute the union of polygons

Shorter version of my question: Is there any polygon union algorithm that allows me to change one of the polygons quickly? Longer version: Currently the major performance bottleneck I'm facing in one ...
1
vote
0answers
21 views

How to cover a surface with a predefined set of objects

I'm making a program that's supposed to be able to find pieces of wood in a dataset to cover a surface. For now I'm focusing on parallelepipedic shapes to simplify the problem (eventually I'd like it ...
0
votes
1answer
37 views

Scaling down a set of points into a smaller area

A visibility graph $G(P) = (V,E)$ of a set $P = \{p_1, \dots, p_n\}$ of points is defined as follows. Each vertex $u \in V$ corresponds to a point $p_u \in P$. There exists an edge $uv \in E$ if, and ...
2
votes
1answer
106 views

Merging all adjacent and overlapping rectangles in a grid to bigger rectangles

I have a 𝑛×𝑚 rectangular grid of cells, and a set 𝑅 of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where ...
3
votes
0answers
34 views

How to get the minimal enclosed polyhedra in a Line framework (points connectivity lists)?

Greetings all and thank you. I'm a Ph.D. candidate working on a force structure's 3D tessellation project and get stuck. I've simplified the system into a set of lines linked together which formed a ...
0
votes
1answer
235 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 $\...
4
votes
1answer
52 views

Can we find the largest intersecting subfamily of convex polygons in quadratic time?

Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (...
0
votes
1answer
102 views

Concentric convex hulls

Given N points in a 2D plane, if we start at a given point and start including points in a set ordered by their distance from the starting point. After including every point, we check if there is a ...
4
votes
1answer
23 views

Binary Plane Partition: do we have to split a line segment?

I'm considering the planar BSP problem, where we are required to partition a set of disjoint line segments in the plane, such that every region in the partition contains at most one line segment or a ...
2
votes
1answer
58 views

How to find simple polygons in a complex polygon created by two lines

Given the image attached, I am looking for a way/strategy/pseudocode to iteratively find each polygon created either by two blue-dotted line segments, a blue-dotted line segment and an intersection, ...
2
votes
1answer
91 views

What is the name of this problem (the dual of the asymmetric k-center problem)

I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse. In this ...
2
votes
1answer
19 views

Understanding contradiction in proof of Algorithm for Testing of Clustering of points in metric space in sub-linear time

I am trying to understand this paper, in which (k, b)-clusterability is defined like so: A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...
1
vote
1answer
20 views

Testing of Clustering of points in metric space in sub-linear time

I am trying to understand this paper, in which (k, b)-clusterability is defined like so: A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...
2
votes
1answer
74 views

Better way to decide if a set is a pure simplicial complex

Setup I am trying to write a function that determines if a set of vertices, edges and faces is a pure simplicial complex. A pure simplicial complex is a set where all facets have the same degree, a ...
2
votes
0answers
40 views

Lower bound 3-dimentional linear programming

I'm reading Computational geometry book. In exercise 4.9 of the mentioned book we encounter the following problem: Suppose we want to find all optimal solution of 3d- linear programming with $n$ ...
0
votes
0answers
21 views

Megiddo's algorithm for finding lowest point in intersection of disks

Given $n$ disks $D_1,D_2,\dots,D_n$ in $\mathbb{R}^2$. We wan to find lowest point in intersection of disks in linear time with extending Megiddo's algorithm. I try as follow: first i divide disks to ...
0
votes
0answers
16 views

Calculating the shortest vector between a vector and a truncated cone

I am trying to understand a certain implementation of calculating the shortest vector between a vector and a truncated cone in 3D. The original idea is introduced in this paper. So if we have two ...
0
votes
1answer
27 views

Nearest Neighbour search with Kirkpatrick's Hierarchy and Re-Triangulating Delaunay after vertex removal

Ok, so I'm having bit of an issue understanding nearest neighbour search with delaunay triangulation. In particular, how do I re-triangulate my delaunay triangulations once I introduced holes? But I ...
3
votes
1answer
76 views

Difference between convex hull algorithms

I was wondering what are the main differences in terms of efficiency of convex hull algorithms? Brute force algorithm is inefficient due to iterating over every three vertices in our set and its time ...
0
votes
1answer
16 views

Finding the distance from a point to a $R^m$ restricted area in $R^n$

The problem is described below: When m=2 and n=3, it is basically finding the distance between a point and a line segment in $R^3$. But when both m and n are larger, do I have to use a generic ...
0
votes
0answers
22 views

How does the railway model of computation get translated to motion on the heptagrid tiling of the hyperbolic plane?

I have been reading these, along with slowly chipping away at the two books Margenstern has produced: A universal cellular automaton in the hyperbolic plane A Universal Cellular Automaton on the ...
0
votes
2answers
96 views

Find the largest rectangle inscribed in a region partitionable into rectangles

Given a rectilinear polygon, what is an run-time efficient algorithm that finds the largest inscribed rectangle the sides of which either parallel or perpendicular to the sides of the rectilinear ...
2
votes
0answers
26 views

Finishing at rest at a target in 2d space

I asked a similar question here, except I forgot to specify that the final velocity must be 0. I have 2 points in 2D space, start = $s$ and target = $t$, and a starting velocity $v_0$. At each time ...
1
vote
1answer
18 views

Vector pathing via acceleration with velocity

I'm trying to solve a scenario where I need to find the smallest number of time steps to reach a location in 2d space, where I can manipulate the velocity with an acceleration at each time step where ...

1
2 3 4 5
15