Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Complexity of the Lower Envelope of Collections of Various Geometric Shapes
Dipartimento di Ingegneria, Università Roma Tre, Italy.
Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).ORCID iD: 0000-0002-2161-6571
Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).ORCID iD: 0000-0002-1342-8618
Linköping University.
Show others and affiliations
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.

Place, publisher, year, edition, pages
2024. Vol. 40, p. 200-206, article id 25
National Category
Computer Sciences Geometry
Identifiers
URN: urn:nbn:se:mau:diva-66642OAI: oai:DiVA.org:mau-66642DiVA, id: diva2:1849752
Conference
40th European Workshop on Computational Geometry, Ioannina, Greece, 2024
Available from: 2024-04-08 Created: 2024-04-08 Last updated: 2024-11-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Abstracts booklet

Authority records

Brötzner, AnnaNilsson, Bengt J.

Search in DiVA

By author/editor
Brötzner, AnnaNilsson, Bengt J.
By organisation
Department of Computer Science and Media Technology (DVMT)
Computer SciencesGeometry

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 217 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf