# Precision-sensitive Euclidean shortest path in 3-space

Joonsoo Choi, Jürgen Sellen, Chee Keng Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

## Abstract

This paper introduces the concept of precision-sensitive algorithms, in analogy to the well-known output-sensitive algorithms. We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path problem. Specifically, we analyze an incremental approximation approach based on ideas in [CSY], and show that this approach yields an asymptotic improvement of running time. By using an optimization technique to improve paths on fixed edge sequences, we modify this algorithm to guarantee a relative error of 0(2-r) in a time polynomial in r and 1/6, where 6 denotes the relative difference in path length between the shortest and the second shortest path. Our result is the best possible in some sense: if we have a strongly precision-sensitive algorithm then we can show that USAT (unambiguous SAT) is in polynomial time, which is widely conjectured to be unlikely. Finally, we discuss the practicability of this approach. Experimental results are provided.

Original language English (US) Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995 Association for Computing Machinery 350-359 10 0897917243 https://doi.org/10.1145/220279.220317 Published - Sep 1 1995 11th Annual Symposium on Computational Geometry, SCG 1995 - Vancouver, CanadaDuration: Jun 5 1995 → Jun 7 1995

### Publication series

Name Proceedings of the Annual Symposium on Computational Geometry Part F129372

### Other

Other 11th Annual Symposium on Computational Geometry, SCG 1995 Canada Vancouver 6/5/95 → 6/7/95

## ASJC Scopus subject areas

• Theoretical Computer Science
• Geometry and Topology
• Computational Mathematics

## Fingerprint

Dive into the research topics of 'Precision-sensitive Euclidean shortest path in 3-space'. Together they form a unique fingerprint.
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8717317581176758, "perplexity": 2303.1616871883393}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2023-14/segments/1679296945381.91/warc/CC-MAIN-20230326013652-20230326043652-00777.warc.gz"}