# Questions tagged [computational-geometry]

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

738 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
97 views

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 (...
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 ...
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 ...
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, ...
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 ...
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$ ...
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$ ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...