The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems
D Marx, A Sidiropoulos - Proceedings of the thirtieth annual symposium …, 2014 - dl.acm.org
We are studying d-dimensional geometric problems that have algorithms with 1− 1/d
appearing in the exponent of the running time, for example, in the form of 2n1− 1/d or nk1 …
appearing in the exponent of the running time, for example, in the form of 2n1− 1/d or nk1 …
On the parameterized complexity of red-blue points separation
We study the following geometric separation problem: Given a set $ R $ of red points and a
set $ B $ of blue points in the plane, find a minimum-size set of lines that separate $ R $ from …
set $ B $ of blue points in the plane, find a minimum-size set of lines that separate $ R $ from …
Stabbing rectangles by line segments-how decomposition reduces the shallow-cell complexity
We initiate the study of the following natural geometric optimization problem. The input is a
set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line …
set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line …
Geometric hitting set for segments of few orientations
SP Fekete, K Huang, JSB Mitchell, O Parekh… - Theory of Computing …, 2018 - Springer
We study several natural instances of the geometric hitting set problem for input consisting of
sets of line segments (and rays, lines) having a small number of distinct slopes. These …
sets of line segments (and rays, lines) having a small number of distinct slopes. These …
[HTML][HTML] Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
Given a permutation π of {1,…, n} and a positive integer k, can π be partitioned into at most k
subsequences, each of which is either increasing or decreasing? We give an algorithm with …
subsequences, each of which is either increasing or decreasing? We give an algorithm with …
On two-handed planar assembly partitioning with connectivity constraints
Assembly planning is a fundamental problem in robotics and automation, which aims to
design a sequence of motions that brings the separate constituent parts of a product into …
design a sequence of motions that brings the separate constituent parts of a product into …
Optimal discretization is fixed-parameter tractable
Given two disjoint sets W 1 and W 2 of points in the plane, the Optimal Discretization
problem asks for the minimum size of a family of horizontal and vertical lines that separate W …
problem asks for the minimum size of a family of horizontal and vertical lines that separate W …
The parameterized complexity of stabbing rectangles
M Dom, MR Fellows, FA Rosamond, S Sikdar - Algorithmica, 2012 - Springer
The NP-complete geometric covering problem Rectangle Stabbing is defined as follows:
Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines …
Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines …
Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing
Given a permutation π of 1,..., n and a positive integer k, we give an algorithm with running
time 2^O(k^2\logk)n^O(1) that decides whether π can be partitioned into at most k increasing …
time 2^O(k^2\logk)n^O(1) that decides whether π can be partitioned into at most k increasing …
Fixed-parameter complexity and approximability of norm maximization
The problem of maximizing the pp th power of ap p-norm over a halfspace-presented
polytope in R^ d R d is a convex maximization problem which plays a fundamental role in …
polytope in R^ d R d is a convex maximization problem which plays a fundamental role in …