|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
23 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Space-Efficient Plane-Sweep Algorithms | | Amr Elmasry
; Frank Kammer
; | | Date: |
7 Jul 2015 | | Abstract: | We introduce space-efficient plane-sweep algorithms for basic planar
geometric problems. It is assumed that the input is in a read-only array of n
items and that the available workspace is $Theta(s)$ bits, where $lg n leq s
leq n cdot lg n$. In particular, we give an almost-optimal algorithm for
finding the closest pair among a set of $n$ points that runs in $O(n^2/s + n
cdot lg s)$ time. We give a simple algorithm to enumerate the intersections
of $n$ line segments whose running time is $O((n^2/s) cdot lg^2 s + k)$,
where $k$ is the number of reported intersections. When the segments are
axis-parallel, we give an $O(n^2/s + n cdot lg s)$-time algorithm for
counting the intersections, and an algorithm for enumerating the intersections
whose running time is $O((n^2/s) cdot lg s cdot lg lg s + n cdot lg s +
k)$. We also present space-efficient algorithms to calculate the measure of $n$
axis-parallel rectangles. | | Source: | arXiv, 1507.1767 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER