Zobrazeno 1 - 10
of 23
pro vyhledávání: '"Panos Giannopoulos"'
Publikováno v:
Abrahamsen, M, Giannopoulos, P, Löffler, M & Rote, G 2020, ' Geometric Multicut : Shortest Fences for Separating Groups of Objects in the Plane ', Discrete & Computational Geometry, vol. 64, pp. 575–607 . https://doi.org/10.1007/s00454-020-00232-w
We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane withkdifferent colours, compute a shortest “fence”F, i.e., a union of curves of minimum total length, that separates every pair of ob
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::33e146a6c303211ed2f8d156ffa90ece
https://doi.org/10.1007/s00454-020-00232-w
https://doi.org/10.1007/s00454-020-00232-w
Communicating the scientific data of the weather forecasts to the general public has always been a challenge. Using computer graphics’ visual representations to convey the message to television viewers and through weather apps and websites has cert
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::27366fdc188d56a810343e27638e6235
https://doi.org/10.5194/ems2021-502
https://doi.org/10.5194/ems2021-502
Autor:
Paweł Rzążewski, Panos Giannopoulos, Marthe Bonamy, Stéphan Thomassé, Nicolas Bousquet, Édouard Bonnet, Pierre Charbit, Florian Sikora, Eun Jung Kim
Publikováno v:
Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
Journal of the ACM (JACM), 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
Journal of the ACM
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
Journal of the ACM (JACM), 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
Journal of the ACM
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematic
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::08e7270d7f539eeb78e1d4fabec534de
https://hal.archives-ouvertes.fr/hal-03107441
https://hal.archives-ouvertes.fr/hal-03107441
We study the complexity of the following cell connection problems in segment arrangements. Given a set of straight-line segments in the plane and two points [Formula: see text] and [Formula: see text] in different cells of the induced arrangement: [(
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::608221153fd3e8dfffe0414b97c5587f
https://openaccess.city.ac.uk/id/eprint/21510/1/connection.pdf
https://openaccess.city.ac.uk/id/eprint/21510/1/connection.pdf
Publikováno v:
ACM Transactions on Algorithms. 7:1-27
We study the parameterized complexity of the k -center problem on a given n -point set P in ℝ d , with the dimension d as the parameter. We show that the rectilinear 3-center problem is fixed-parameter tractable, by giving an algorithm that runs in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::41e9a7a276a42de9b6e8b1be579b31a8
https://doi.org/10.1145/2000807.2000811
https://doi.org/10.1145/2000807.2000811
Publikováno v:
International Journal of Computational Geometry & Applications. 20:147-173
We prove that computing a geometric minimum-dilation graph on a given set of points in the plane, using not more than a given number of edges, is an NP-hard problem, no matter if edge crossings are allowed or forbidden. We also show that the problem
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::33f87fa083e6ea2845431b970d493ea5
https://doi.org/10.1142/s0218195910003244
https://doi.org/10.1142/s0218195910003244
Publikováno v:
SIAM Journal on Computing, 38(1), 226-240. Society for Industrial and Applied Mathematics (SIAM)
Given a Euclidean graph $G$ in $\mathbb{R}^d$ with $n$ vertices and $m$ edges, we consider the problem of adding an edge to $G$ such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stret
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c5a3442e552e5122c034f930f8675f97
https://doi.org/10.1137/050635675
https://doi.org/10.1137/050635675
Publikováno v:
Information Processing Letters. 105:73-77
Deciding whether two n-point sets A, B ∈ℝ d are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::32d9e270fe47dfb70279efc353c77713
https://doi.org/10.1016/j.ipl.2007.08.003
https://doi.org/10.1016/j.ipl.2007.08.003
Publikováno v:
The Computer Journal. 51:372-384
This paper surveys parameterized complexity results for hard geometric algorithmic problems. It includes fixed-parameter tractable problems in graph drawing, geometric graphs, geometric covering and several other areas, together with an overview of t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f292bd9147d5e09073bb38613b85fb4f
https://doi.org/10.1093/comjnl/bxm053
https://doi.org/10.1093/comjnl/bxm053
Autor:
Panos Giannopoulos, Sergio Cabello
Publikováno v:
Symposium on Computational Geometry
Scopus-Elsevier
Scopus-Elsevier
We study the following separation problem: given $$n$$n connected curves and two points $$s$$s and $$t$$t in the plane, compute the minimum number of curves one needs to retain so that any path connecting $$s$$s to $$t$$t intersects some of the retai
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::928bdfa433eeaf7a74732cc9b61882e4
https://doi.org/10.1145/2462356.2462383
https://doi.org/10.1145/2462356.2462383