Optimizing squares covering a set of points
| Autor: | Binay K. Bhattacharya, Priya Ranjan Sinha Mahapatra, Zhao Song, Sandip Das, Sergey Bereg, Tsunehiko Kameda |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Convex hull Polynomial General Computer Science 0102 computer and information sciences 02 engineering and technology Disjoint sets Difference of two squares 01 natural sciences Least squares Square (algebra) Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Non-linear least squares 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Total least squares Mathematics |
| Zdroj: | Theoretical Computer Science. 729:68-83 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2015.11.029 |
| Popis: | We investigate two kinds of optimization problems regarding points in the 2-dimensional plane that need to be enclosed by squares. (1) Given a set of \(n\) points, find a given number of squares that enclose all the points, minimizing the size of the largest square used. (2) Given a set of \(n\) points, enclose the maximum number of points, using a specified number of squares of a fixed size. We provide different techniques to solve the above problems in cases where squares are axis-parallel or of arbitrary orientation, disjoint or overlapping. All the algorithms we use run in time that is a low-order polynomial in \(n\). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect