### Abstract

The Point Hyperplane Cover problem in ℝ^{d} takes as input a set of n points in ℝ^{d} and a positive integer k. The objective is to cover all the given points with a set of at most k hyperplanes. The D-Polynomial Points Hitting Set (D-Polynomial Points HS) problem in ℝ^{d} takes as input a family F of D-degree polynomials from a vector space R in ℝ^{d}, and determines whether there is a set of at most k points in ℝ^{d} that hit all the polynomials in F. For both problems, we exhibit tight kernels where k is the parameter.

Original language | English |
---|---|

Title of host publication | LATIN 2018: Theoretical Informatics |

Subtitle of host publication | 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings |

Editors | M.A. Bender, M. Farach-Colton, M.A. Mosteiro |

Place of Publication | Dordrecht |

Publisher | Springer |

Pages | 187-200 |

Number of pages | 14 |

ISBN (Electronic) | 978-3-319-77404-6 |

ISBN (Print) | 978-3-319-77403-9 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

Event | 13th Latin American Theoretical INformatics Symposium (LATIN 2018) - Buenos Aires, Argentina Duration: 16 Apr 2018 → 19 Apr 2018 Conference number: 13 http://latin2018.dc.uba.ar/ |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10807 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 13th Latin American Theoretical INformatics Symposium (LATIN 2018) |
---|---|

Abbreviated title | LATIN 2018 |

Country | Argentina |

City | Buenos Aires |

Period | 16/04/18 → 19/04/18 |

Internet address |

### Fingerprint

### Cite this

*LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings*(pp. 187-200). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS). Dordrecht: Springer. https://doi.org/10.1007/978-3-319-77404-6_15

}

*LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10807 LNCS, Springer, Dordrecht, pp. 187-200, 13th Latin American Theoretical INformatics Symposium (LATIN 2018), Buenos Aires, Argentina, 16/04/18. https://doi.org/10.1007/978-3-319-77404-6_15

**Tight kernels for covering and hitting : Point hyperplane cover and polynomial point hitting set.** / Boissonnat, Jean Daniel; Dutta, Kunal; Ghosh, Arijit; Kolay, Sudeshna.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Tight kernels for covering and hitting

T2 - Point hyperplane cover and polynomial point hitting set

AU - Boissonnat, Jean Daniel

AU - Dutta, Kunal

AU - Ghosh, Arijit

AU - Kolay, Sudeshna

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The Point Hyperplane Cover problem in ℝd takes as input a set of n points in ℝd and a positive integer k. The objective is to cover all the given points with a set of at most k hyperplanes. The D-Polynomial Points Hitting Set (D-Polynomial Points HS) problem in ℝd takes as input a family F of D-degree polynomials from a vector space R in ℝd, and determines whether there is a set of at most k points in ℝd that hit all the polynomials in F. For both problems, we exhibit tight kernels where k is the parameter.

AB - The Point Hyperplane Cover problem in ℝd takes as input a set of n points in ℝd and a positive integer k. The objective is to cover all the given points with a set of at most k hyperplanes. The D-Polynomial Points Hitting Set (D-Polynomial Points HS) problem in ℝd takes as input a family F of D-degree polynomials from a vector space R in ℝd, and determines whether there is a set of at most k points in ℝd that hit all the polynomials in F. For both problems, we exhibit tight kernels where k is the parameter.

UR - http://www.scopus.com/inward/record.url?scp=85045377208&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-77404-6_15

DO - 10.1007/978-3-319-77404-6_15

M3 - Conference contribution

AN - SCOPUS:85045377208

SN - 978-3-319-77403-9

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 187

EP - 200

BT - LATIN 2018: Theoretical Informatics

A2 - Bender, M.A.

A2 - Farach-Colton, M.

A2 - Mosteiro, M.A.

PB - Springer

CY - Dordrecht

ER -