Multi-Target Search in Euclidean Space with Ray Shooting (Full Version) Article Swipe
Ryan Hechenberger
,
Daniel Harabor
,
Muhammad Aamir Cheema
,
Peter J. Stuckey
,
Pierre Le Bodic
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2207.02436
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2207.02436
The Euclidean shortest path problem (ESPP) is a well studied problem with many practical applications. Recently a new efficient online approach to this problem, RayScan, has been developed, based on ray shooting and polygon scanning. In this paper we show how we can improve RayScan by carefully reasoning about polygon scans. We also look into how RayScan could be applied in the single-source multi-target scenario, where logic during scanning is used to reduce the number of rays shots required. This improvement also helps in the single target case. We compare the improved RayScan+ against the state-of-the-art ESPP algorithm, illustrating the situations where it is better.
Related Topics To Compare & Contrast
Concepts
Polygon (computer graphics)
Computer science
Euclidean distance
Euclidean geometry
Algorithm
Path (computing)
Shortest path problem
Space (punctuation)
Computer vision
Computer graphics (images)
Artificial intelligence
Theoretical computer science
Mathematical optimization
Mathematics
Geometry
Programming language
Frame (networking)
Telecommunications
Graph
Operating system
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2207.02436
- https://arxiv.org/pdf/2207.02436
- OA Status
- green
- Cited By
- 3
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4284892159
All OpenAlex metadata
Raw OpenAlex JSON
No additional metadata available.