Publikationer från Malmö universitet
Ändra sökning
Avgränsa sökresultatet
1 - 7 av 7
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1.
    Aichholzer, Oswin
    et al.
    Graz University of Technology, Austria.
    Anna, Brötzner
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Bicolored Order Types2024Ingår i: Computing in Geometry and Topology, ISSN 2750-7823, Vol. 3, nr 2Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In their seminal work on Multidimensional Sorting, Goodman and Pollack introduced the so-called order type, which for each ordered triple of a point set in the plane gives its orientation, clockwise or counterclockwise. This information is sufficient to solve many problems from discrete geometry where properties of point sets do not depend on the exact coordinates of the points but only on their relative positions. Goodman and Pollack showed that an efficient way to store an order type in a matrix λ of quadratic size (w.r.t. the number of points) is to count for every oriented line spanned by two points of the set how many of the remaining points lie to the left of this line. We generalize the concept of order types to bicolored point sets (every point has one of two colors). The bicolored order type contains the orientation of each bicolored triple of points, while no information is stored for monochromatic triples. Similar to the uncolored case, we store the number of blue points that are to the left of an oriented line spanned by two red points or by one red and one blue point in λB. Analogously the number of red points is stored in λR. As a main result, we show that the equivalence of the information contained in the orientation of all bicolored point triples and the two matrices λB and λR also holds in the colored case. This is remarkable, as in general the bicolored order type does not even contain sufficient information to determine all extreme points (points on the boundary of the convex hull of the point set).We then show that the information of a bicolored order type is sufficient to determine whether the two color classes can be linearly separated and how one color class can be sorted around a point of the other color class. Moreover, knowing the bicolored order type of a point set suffices to find bicolored plane perfect matchings or to compute the number of crossings of the complete bipartite graph drawn on a bicolored point set in quadratic time.

    Ladda ner fulltext (pdf)
    fulltext
  • 2. Balko, Martin
    et al.
    Anna, Brötzner
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Klute, Fabian
    Tkadlec, Josef
    Faces in Rectilinear Drawings of Complete Graphs2024Ingår i: 40th European Workshop on Computational Geometry: Booklet of abstracts, 2024, Vol. 40, s. 69-75, artikel-id 8Konferensbidrag (Refereegranskat)
    Abstract [en]

    We study extremal problems about faces in convex rectilinear drawings of Kn, that is, drawings where vertices are represented by points in the plane in convex position and edges by line segments between the points representing the end-vertices. We show that if a convex rectilinear drawing of Kn does not contain a common interior point of at least three edges, then there is always a face forming a convex 5-gon while there are such drawings without any face forming a convex k-gon with k ≥ 6.

    A convex rectilinear drawing of Kn is regular if its vertices correspond to vertices of a regular convex n-gon. We characterize positive integers n for which regular drawings of Kn contain a face forming a convex 5-gon.

    To our knowledge, this type of problems has not been considered in the literature before and so we also pose several new natural open problems.

  • 3.
    Aichholzer, Oswin
    et al.
    Graz University of Technology.
    Anna, Brötzner
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Perz, Daniel
    Schnider, Patrick
    Department of Computer Science, ETH Zürich.
    Flips in Odd Matchings2024Ingår i: 40th European Workshop on Computational Geometry: Booklet of abstracts, 2024, Vol. 40, s. 447-452, artikel-id 59Konferensbidrag (Refereegranskat)
    Abstract [en]

    Let P be a set of n = 2m + 1 points in the plane in general position. We define the graph GMP whose vertex set is the set of all plane matchings on P with exactly m edges. Two vertices in GMP are connected if the two corresponding matchings have m − 1 edges in common. In this work we show that GMP is connected.

  • 4.
    Alegría, Carlos
    et al.
    Dipartimento di Ingegneria, Università Roma Tre, Italy.
    Anna, Brötzner
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Nilsson, Bengt J.
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Schmidt, Christiane
    Linköping University.
    Seara, Carlos
    Department of Mathematics, Universidad Politécnica de Catalunya, Spain.
    The Complexity of the Lower Envelope of Collections of Various Geometric Shapes2024Ingår i: 40th European Workshop on Computational Geometry: Booklet of abstracts, 2024, Vol. 40, s. 200-206, artikel-id 25Konferensbidrag (Refereegranskat)
    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.

  • 5.
    Anna, Brötzner
    et al.
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Nilsson, Bengt J.
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Schmidt, Christiane
    Linköping University.
    The k-Transmitter Watchman Route Problem is NP-Hard Even in Histograms and Star-Shaped Polygons2024Ingår i: 40th European Workshop on Computational Geometry: Booklet of abstracts, 2024, Vol. 40, s. 381-387, artikel-id 50Konferensbidrag (Refereegranskat)
    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.

  • 6.
    Bagheri, Alireza
    et al.
    Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran.
    Anna, Brötzner
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Farivar, Faezeh
    Science and Research Branch, Islamic Azad University, Tehran, Iran.
    Ghasemi, Rahmat
    Science and Research Branch, Islamic Azad University, Tehran, Iran.
    Keshavarz-Kohjerdi, Fatemeh
    Shahed University, Tehran, Iran.
    Krohn, Erik
    University of Wisconsin, Oshkosh, USA.
    Nilsson, Bengt J.
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Schmidt, Christiane
    Linköping University, Campus Norrköping, Sweden.
    Minsum m watchmen’s routes in Stiegl polygons2023Ingår i: XX Spanish Meeting on Computational Geometry: Book of Abstracts, 2023, Vol. 20, s. 41-44, artikel-id 21Konferensbidrag (Refereegranskat)
    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.

    Ladda ner fulltext (pdf)
    fulltext
  • 7.
    Oswin, Aichholzer
    et al.
    Graz University of Technology, Graz, Austria.
    Anna, Brötzner
    Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).
    Two Equivalent Representations of Bicolored Order Types2023Ingår i: 39th European Workshop on Computational Geometry: Book of Abstracts, 2023, Vol. 39, s. 12-17, artikel-id 1Konferensbidrag (Övrigt vetenskapligt)
    Abstract [en]

    In their seminal work on Multidimensional Sorting, Goodman and Pollack introduced the so-called order type, which for each ordered triple of a point set in the plane gives its orientation, clockwise or counterclockwise. This information is sufficient to solve many problems from discrete geometry where properties of point sets do not depend on the exact coordinates of the points but only on their relative positions. Goodman and Pollack showed that an efficient way to store an order type in a matrix λ of quadratic size (w.r.t. the number of points) is to count for every oriented line spanned by two points of the set how many of the remaining points lie to the left of this line.

    We generalize the concept of order types to bicolored point sets (every point has one of two colors). The bicolored order type contains the orientation of each bicolored triple of points, while no information is stored for monochromatic triples. Similar to the uncolored case, we store the number of blue points that are to the left of an oriented line spanned by two red points or by one red and one blue point in λB. Analogously the number of red points is stored in λR.

    We show that the equivalence of the information contained in the orientation of all bicolored point triples and the two matrices λB and λR also holds in the colored case. This is remarkable, as in general the bicolored order type does not even contain sufficient information to determine all extreme points (points on the boundary of the convex hull of the point set).

    Ladda ner fulltext (pdf)
    fulltext
1 - 7 av 7
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf