License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.25
URN: urn:nbn:de:0030-drops-80863
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8086/
Boissonnat, Jean-Daniel ;
Dutta, Kunal ;
Ghosh, Arijit ;
Kolay, Sudeshna
Kernelization of the Subset General Position Problem in Geometry
Abstract
In this paper, we consider variants of the Geometric Subset General Position problem. In defining this problem, a geometric subsystem is specified, like a subsystem of lines, hyperplanes or spheres. The input of the problem is a set of n points in \mathbb{R}^d and a positive integer k. The objective is to find a subset of at least k input points such that this subset is in general position with respect to the specified subsystem. For example, a set of points is in
general position with respect to a subsystem of hyperplanes in \mathbb{R}^d if no d+1 points lie on the same
hyperplane. In this paper, we study the Hyperplane Subset General Position problem under two parameterizations.
When parameterized by k then we exhibit a polynomial kernelization for the problem. When parameterized by h=n-k,
or the dual parameter, then we exhibit polynomial kernels which are also tight, under standard complexity theoretic
assumptions.
We can also exhibit similar kernelization results for d-Polynomial Subset General Position, where a vector space of polynomials
of degree at most d are specified as the underlying subsystem such that the size of the basis for this vector space is b. The objective is to find a set of at least k input points, or in the dual delete at most h = n-k points, such that no b+1 points lie on the same polynomial. Notice that this is a generalization of many well-studied geometric variants of the Set Cover problem, such as Circle Subset General Position. We also study general projective variants of these problems. These problems are also related to other geometric problems like Subset Delaunay Triangulation problem.
BibTeX - Entry
@InProceedings{boissonnat_et_al:LIPIcs:2017:8086,
author = {Jean-Daniel Boissonnat and Kunal Dutta and Arijit Ghosh and Sudeshna Kolay},
title = {{Kernelization of the Subset General Position Problem in Geometry}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {25:1--25:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-046-0},
ISSN = {1868-8969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8086},
URN = {urn:nbn:de:0030-drops-80863},
doi = {10.4230/LIPIcs.MFCS.2017.25},
annote = {Keywords: Incidence Geometry, Kernel Lower bounds, Hyperplanes, Bounded degree polynomials}
}
|
Keywords: |
|
Incidence Geometry, Kernel Lower bounds, Hyperplanes, Bounded degree polynomials |
|
Collection: |
|
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.12.2017 |
