Sökning: id:"swepub:oai:DiVA.org:mau-66642" >
The Complexity of t...
The Complexity of the Lower Envelope of Collections of Various Geometric Shapes
-
- Alegría, Carlos (författare)
- Dipartimento di Ingegneria, Università Roma Tre, Italy
-
- Anna, Brötzner (författare)
- Malmö universitet,Institutionen för datavetenskap och medieteknik (DVMT)
-
- Nilsson, Bengt J. (författare)
- Malmö universitet,Institutionen för datavetenskap och medieteknik (DVMT)
-
visa fler...
-
- Schmidt, Christiane (författare)
- Linköping University
-
- Seara, Carlos (författare)
- Department of Mathematics, Universidad Politécnica de Catalunya, Spain
-
visa färre...
-
(creator_code:org_t)
- 2024
- 2024
- Engelska.
-
Ingår i: 40th European Workshop on Computational Geometry. ; , s. 200-206
- Relaterad länk:
-
https://eurocg2024.m...
-
visa fler...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
- NATURVETENSKAP -- Matematik -- Geometri (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Geometry (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)