Malmö University Publications
Change search
Link to record
Permanent link

Direct link
Alternative names
Publications (10 of 46) Show all publications
Alegría, C., Anna, B., Nilsson, B. J., Schmidt, C. & Seara, C. (2024). The Complexity of the Lower Envelope of Collections of Various Geometric Shapes. In: 40th European Workshop on Computational Geometry: Booklet of abstracts. Paper presented at 40th European Workshop on Computational Geometry, Ioannina, Greece, 2024 (pp. 200-206). , 40, Article ID 25.
Open this publication in new window or tab >>The Complexity of the Lower Envelope of Collections of Various Geometric Shapes
Show others...
2024 (English)In: 40th European Workshop on Computational Geometry: Booklet of abstracts, 2024, Vol. 40, p. 200-206, article id 25Conference paper, Oral presentation with published abstract (Refereed)
Abstract [en]

We study the problem of determining the complexity of the lower envelope of a collection of n geometric objects. For collections of rays; unit length line segments; and collections of unit squares to which we apply at most two transformations from translation, rotation, and scaling, we prove a complexity of Θ(n). If all three transformations are applied to unit squares, then we show the complexity becomes Θ(nα(n)), where α(n) is the slowly growing inverse of Ackermann’s function.

National Category
Computer Sciences Geometry
Identifiers
urn:nbn:se:mau:diva-66642 (URN)
Conference
40th European Workshop on Computational Geometry, Ioannina, Greece, 2024
Available from: 2024-04-08 Created: 2024-04-08 Last updated: 2024-04-09Bibliographically approved
Anna, B., Nilsson, B. J. & Schmidt, C. (2024). The k-Transmitter Watchman Route Problem is NP-Hard Even in Histograms and Star-Shaped Polygons. In: 40th European Workshop on Computational Geometry: Booklet of abstracts. Paper presented at 40th European Workshop on Computational Geometry, Ioannina, Greece, 2024 (pp. 381-387). , 40, Article ID 50.
Open this publication in new window or tab >>The k-Transmitter Watchman Route Problem is NP-Hard Even in Histograms and Star-Shaped Polygons
2024 (English)In: 40th European Workshop on Computational Geometry: Booklet of abstracts, 2024, Vol. 40, p. 381-387, article id 50Conference paper, Oral presentation with published abstract (Refereed)
Abstract [en]

A k-transmitter g in a polygon P, with n vertices, k-sees a point pP if the line segment gp intersects P’s boundary at most k times. In the k-Transmitter Watchman Route Problem we aim to minimize the length of a k-transmitter watchman route along which every point in the polygon—or a discrete set of points in the interior of the polygon—is k-seen. We show that the k-Transmitter Watchman Route Problem for a discrete set of points is NP-hard for histograms, uni-monotone polygons, and star-shaped polygons given a fixed starting point. For histograms and uni-monotone polygons it is also NP-hard without a fixed starting point. Moreover, none of these versions can be approximated to within a factor c · log n, for any constant c > 0.

National Category
Computer Sciences Geometry
Identifiers
urn:nbn:se:mau:diva-66643 (URN)
Conference
40th European Workshop on Computational Geometry, Ioannina, Greece, 2024
Available from: 2024-04-08 Created: 2024-04-08 Last updated: 2024-04-09Bibliographically approved
Nilsson, B. J. & Schmidt, C. (2023). k-Transmitter Watchman Routes. In: WALCOM: Algorithms and Computation: 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings. Paper presented at 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023 (pp. 202-213). Springer
Open this publication in new window or tab >>k-Transmitter Watchman Routes
2023 (English)In: WALCOM: Algorithms and Computation: 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings, Springer, 2023, p. 202-213Conference paper, Published paper (Refereed)
Abstract [en]

We consider the watchman route problem for a k-transmitter watchman: standing at point p in a polygon P, the watchman can see �∈� if ��¯ intersects P’s boundary at most k times—q is k-visible to p. Traveling along the k-transmitter watchman route, either all points in P or a discrete set of points �⊂� must be k-visible to the watchman. We aim for minimizing the length of the k-transmitter watchman route.

We show that even in simple polygons the shortest k-transmitter watchman route problem for a discrete set of points �⊂� is NP-complete and cannot be approximated to within a logarithmic factor (unless P=NP), both with and without a given starting point. Moreover, we present a polylogarithmic approximation for the k-transmitter watchman route problem for a given starting point and �⊂� with approximation ratio �(log2⁡(|�|⋅�)log⁡log⁡(|�|⋅�)log⁡|�|) (with |�|=�).

Place, publisher, year, edition, pages
Springer, 2023
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 13973
National Category
Computational Mathematics
Identifiers
urn:nbn:se:mau:diva-64307 (URN)10.1007/978-3-031-27051-2_18 (DOI)2-s2.0-85151057723 (Scopus ID)978-3-031-27050-5 (ISBN)978-3-031-27051-2 (ISBN)
Conference
17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023
Available from: 2023-12-12 Created: 2023-12-12 Last updated: 2023-12-12Bibliographically approved
Bagheri, A., Anna, B., Farivar, F., Ghasemi, R., Keshavarz-Kohjerdi, F., Krohn, E., . . . Schmidt, C. (2023). Minsum m watchmen’s routes in Stiegl polygons. In: XX Spanish Meeting on Computational Geometry: Book of Abstracts. Paper presented at XX Spanish Meeting on Computational Geometry, Santiago de Compostela, Spain, July 3-5,2023 (pp. 41-44). , 20, Article ID 21.
Open this publication in new window or tab >>Minsum m watchmen’s routes in Stiegl polygons
Show others...
2023 (English)In: XX Spanish Meeting on Computational Geometry: Book of Abstracts, 2023, Vol. 20, p. 41-44, article id 21Conference paper, Published paper (Refereed)
Abstract [en]

We present an O(n2 · min{m, n}) time and O(n · min{m, n}) storage algorithm to compute the minsum set of m watchmen routes given their starting points in a Stiegl polygon ― a staircase polygon where the floor solely consists of one horizontal and one vertical edge ― with n vertices.

Keywords
Computational Geometry, Art Gallery Problems, Watchman Routes
National Category
Discrete Mathematics Geometry Computer Sciences
Identifiers
urn:nbn:se:mau:diva-63976 (URN)
Conference
XX Spanish Meeting on Computational Geometry, Santiago de Compostela, Spain, July 3-5,2023
Funder
Swedish Research Council
Available from: 2023-12-06 Created: 2023-12-06 Last updated: 2023-12-06Bibliographically approved
Ashvinkumar, V., Gudmundsson, J., Levcopoulos, C., Nilsson, B. J. & van Renssen, A. (2022). Local Routing in Sparse and Lightweight Geometric Graphs. Algorithmica, 84, 1316-1340
Open this publication in new window or tab >>Local Routing in Sparse and Lightweight Geometric Graphs
Show others...
2022 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 84, p. 1316-1340Article in journal (Refereed) Published
Abstract [en]

Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O (1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin (SIAM J Comput 33(4):937-951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega (n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O (1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O (1)-competitive routing strategy.

Place, publisher, year, edition, pages
Springer, 2022
Keywords
Computational geometry, Spanners, Routing
National Category
Computer Sciences
Identifiers
urn:nbn:se:mau:diva-49961 (URN)10.1007/s00453-022-00930-2 (DOI)000746779100001 ()2-s2.0-85123504940 (Scopus ID)
Available from: 2022-02-07 Created: 2022-02-07 Last updated: 2024-02-05Bibliographically approved
Gibson-Lopez, M., Krohn, E., Nilsson, B. J., Rayford, M., Soderman, S. & Żyliński, P. (2022). On Vertex Guarding Staircase Polygons. In: Armando Castañeda; Francisco Rodríguez-Henríquez (Ed.), LATIN 2022: Theoretical Informatics. LATIN 2022: . Paper presented at 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings (pp. 746-760). Springer
Open this publication in new window or tab >>On Vertex Guarding Staircase Polygons
Show others...
2022 (English)In: LATIN 2022: Theoretical Informatics. LATIN 2022 / [ed] Armando Castañeda; Francisco Rodríguez-Henríquez, Springer, 2022, p. 746-760Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we consider the variant of the art gallery problem where the input polygon is a staircase polygon. Previous works on this problem gave a 2-approximation for point guarding a staircase polygon (where guards can be placed anywhere in the interior of the polygon and we wish to guard the entire polygon). It is still unknown whether this point guarding variant is NP-hard. In this paper we consider the vertex guarding problem, where guards are only allowed to be placed at the vertices of the polygon, and we wish to guard only the vertices of the polygon. We show that this problem is NP-hard, and we give a polynomial-time 2-approximation algorithm. 

Place, publisher, year, edition, pages
Springer, 2022
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 13568
National Category
Computer Sciences
Identifiers
urn:nbn:se:mau:diva-57000 (URN)10.1007/978-3-031-20624-5_45 (DOI)2-s2.0-85144549579 (Scopus ID)
Conference
15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings
Available from: 2023-01-02 Created: 2023-01-02 Last updated: 2024-02-05Bibliographically approved
Krohn, E., Nilsson, B. J. & Schmidt, C. (2022). Opposing Half Guards. In: 34th Canadian Conference on Computational Geometry: . Paper presented at 34th Canadian Conference on Computational Geometry (CCCG 2022), 25-27 August 2022, Toronto, Canada.
Open this publication in new window or tab >>Opposing Half Guards
2022 (English)In: 34th Canadian Conference on Computational Geometry, 2022Conference paper, Published paper (Refereed)
Abstract [en]

We study the art gallery problem for opposing halfguards: guards that can either see to their left or to theirright only. We present art gallery theorems, show thatthe problem is NP-hard in monotone polygons, presentapproximation algorithms for spiral and staircase poly-gons, and show that the location of half guards in 2-guardable polygons is not restricted to extensions.

National Category
Computer Sciences
Identifiers
urn:nbn:se:mau:diva-64333 (URN)2-s2.0-85173825842 (Scopus ID)
Conference
34th Canadian Conference on Computational Geometry (CCCG 2022), 25-27 August 2022, Toronto, Canada
Funder
Swedish Research Council, 2021-03810Swedish Research Council, 2018-0400
Available from: 2023-12-12 Created: 2023-12-12 Last updated: 2023-12-12Bibliographically approved
Nilsson, B. J., Orden, D., Palios, L., Seara, C. & Żyliński, P. (2021). Illuminating the x-Axis by α-Floodlights. In: Ahn, Hee-Kap; Sadakane, Kunihiko (Ed.), 32nd International Symposium on Algorithms and Computation (ISAAC 2021): . Paper presented at 32nd International Symposium on Algorithms and Computation (ISAAC 2021).
Open this publication in new window or tab >>Illuminating the x-Axis by α-Floodlights
Show others...
2021 (English)In: 32nd International Symposium on Algorithms and Computation (ISAAC 2021) / [ed] Ahn, Hee-Kap; Sadakane, Kunihiko, 2021Conference paper, Published paper (Refereed)
Abstract [en]

Given a set S of regions with piece-wise linear boundary and a positive angle α < 90°, we consider the problem of computing the locations and orientations of the minimum number of α-floodlights positioned at points in S which suffice to illuminate the entire x-axis. We show that the problem can be solved in O(n log n) time and O(n) space, where n is the number of vertices of the set S.

Keywords
Computational Geometry, Visibility, Art Gallery Problems, Floodlight
National Category
Computer Sciences
Identifiers
urn:nbn:se:mau:diva-56852 (URN)10.4230/LIPIcs.ISAAC.2021.11 (DOI)2-s2.0-85122431081 (Scopus ID)978-3-95977-214-3 (ISBN)
Conference
32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Available from: 2022-12-20 Created: 2022-12-20 Last updated: 2024-02-05Bibliographically approved
Nilsson, B. J. & Vujovic, G. (2021). Online Two-Dimensional Vector Packing with Advice. In: Tiziana Calamoneri and Federico Corò (Ed.), Proc. 12th International Conference on Algorithms and Complexity, CIAC'2021: . Paper presented at Algorithms and Complexity, CIAC'2021 (pp. 381-393). Springer, 12701
Open this publication in new window or tab >>Online Two-Dimensional Vector Packing with Advice
2021 (English)In: Proc. 12th International Conference on Algorithms and Complexity, CIAC'2021 / [ed] Tiziana Calamoneri and Federico Corò, Springer, 2021, Vol. 12701, p. 381-393Conference paper, Published paper (Refereed)
Abstract [en]

We consider the online two-dimensional vector packing problem, showing a lower bound of 11/5 on the competitive ratio of any AnyFit strategy for the problem. We provide a strategy with competitive ratio max{2,6/(1+3tan(𝜋/4−𝛾/2))+𝜖}max{2,6/(1+3tan⁡(π/4−γ/2))+ϵ} and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range [𝜋/4−𝛾/2,𝜋/4+𝛾/2][π/4−γ/2,π/4+γ/2], for 0≤𝛾<𝜋/30≤γ<π/3. In addition, we give a 5/2-competitive strategy also using logarithmic advice for the unrestricted vectors case. These results should be contrasted to the currently best competitive strategy, FirstFit, having competitive ratio 27/10.

Place, publisher, year, edition, pages
Springer, 2021
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 12701
Keywords
Bin Packing, Vector Packing, Online Computation, Competitive Analysis, Advice Complexity
National Category
Computer Sciences
Identifiers
urn:nbn:se:mau:diva-42285 (URN)10.1007/978-3-030-75242-2_27 (DOI)2-s2.0-85106204800 (Scopus ID)978-3-030-75241-5 (ISBN)978-3-030-75242-2 (ISBN)
Conference
Algorithms and Complexity, CIAC'2021
Available from: 2021-05-23 Created: 2021-05-23 Last updated: 2024-02-05Bibliographically approved
Paraschakis, D. & Nilsson, B. J. (2020). FlowRec: Prototyping Session-based Recommender Systemsin Streaming Mode. In: PAKDD 2020: Advances in Knowledge Discovery and Data Mining. Paper presented at 24th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2020. Springer
Open this publication in new window or tab >>FlowRec: Prototyping Session-based Recommender Systemsin Streaming Mode
2020 (English)In: PAKDD 2020: Advances in Knowledge Discovery and Data Mining, Springer, 2020Conference paper, Published paper (Refereed)
Abstract [en]

Despite the increasing interest towards session-based and streaming recommender systems, there is still a lack of publicly available evaluation frameworks supporting both these paradigms. To address the gap, we propose FlowRec — an extension of the streaming framework Scikit-Multiflow, which opens plentiful possibilities for prototyping recommender systems operating on sessionized data streams, thanks to the underlying collection of incremental learners and support for real-time performance tracking. We describe the extended functionalities of the adapted prequential evaluation protocol, and develop a competitive recommendation algorithm on top of Scikit-Multiflow’s implementation of a Hoeffding Tree. We compare our algorithm to other known baselines for the next-item prediction task across three different domains.

Place, publisher, year, edition, pages
Springer, 2020
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 12084
Keywords
Streaming recommendations, Session-based recommendations, Prequential evaluation, Online learning, Hoeffding Tree
National Category
Computer Sciences
Identifiers
urn:nbn:se:mau:diva-17191 (URN)10.1007/978-3-030-47426-3_6 (DOI)000716986400006 ()2-s2.0-85085731034 (Scopus ID)978-3-030-47425-6 (ISBN)978-3-030-47426-3 (ISBN)
Conference
24th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2020
Available from: 2020-05-07 Created: 2020-05-07 Last updated: 2024-02-05Bibliographically approved
Projects
Internet of Things Master's Program; Malmö University
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-1342-8618

Search in DiVA

Show all publications