Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2203.12333 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911438315978752 |
|---|---|
| author | Ghorbal, Khalil Kozaily, Christelle |
| author_facet | Ghorbal, Khalil Kozaily, Christelle |
| contents | This paper is concerned with a covering problem of Euclidean space by a particular arrangement of cones that are not necessarily full and are allowed to overlap. The problem provides an equivalent geometric reformulation of the solvability of the linear complementarity problem defining the class of Q-matrices. Assuming feasibility, we rely on standard tools from convex geometry to study maximal connected uncovered regions, we term \emph{holes}. We then use our approach to fully characterize the problem for dimension $3$, regardless of degeneracy. We further provide, for $n \leq 3$, an algebraic characterization for the class of Q-matrices. That is, we show that, $M$ is a Q-matrix if and only if its entries belong to an explicit semi-algebraic set (in dimension $9$) where all the involved polynomials are subdeterminants of $M$. We showcase the usefulness of such a characterization by generating $3$-by-$3$ Q-matrices with specific interesting properties on the involved cones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_12333 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On Covering Euclidean Space with Q-arrangements of Cones Ghorbal, Khalil Kozaily, Christelle Optimization and Control 90C33, 68W30, 03C10 This paper is concerned with a covering problem of Euclidean space by a particular arrangement of cones that are not necessarily full and are allowed to overlap. The problem provides an equivalent geometric reformulation of the solvability of the linear complementarity problem defining the class of Q-matrices. Assuming feasibility, we rely on standard tools from convex geometry to study maximal connected uncovered regions, we term \emph{holes}. We then use our approach to fully characterize the problem for dimension $3$, regardless of degeneracy. We further provide, for $n \leq 3$, an algebraic characterization for the class of Q-matrices. That is, we show that, $M$ is a Q-matrix if and only if its entries belong to an explicit semi-algebraic set (in dimension $9$) where all the involved polynomials are subdeterminants of $M$. We showcase the usefulness of such a characterization by generating $3$-by-$3$ Q-matrices with specific interesting properties on the involved cones. |
| title | On Covering Euclidean Space with Q-arrangements of Cones |
| topic | Optimization and Control 90C33, 68W30, 03C10 |
| url | https://arxiv.org/abs/2203.12333 |