Sublinear geometric algorithms

Bernard Chazelle; Ding Liu; Avner Magen

doi:10.1137/S009753970444572X

Sublinear geometric algorithms

Bernard Chazelle, Ding Liu, Avner Magen

Research output: Contribution to journal › Article › peer-review

25 Scopus citations

Abstract

We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.

Original language	English (US)
Pages (from-to)	627-646
Number of pages	20
Journal	SIAM Journal on Computing
Volume	35
Issue number	3
DOIs	https://doi.org/10.1137/S009753970444572X
State	Published - 2005
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Keywords

Approximate shortest paths
Polyhedral intersection
Sublinear algorithms

Access to Document

10.1137/S009753970444572X

Cite this

@article{91a59ca9971344c593ffe000d18204d8,

title = "Sublinear geometric algorithms",

abstract = "We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.",

keywords = "Approximate shortest paths, Polyhedral intersection, Sublinear algorithms",

author = "Bernard Chazelle and Ding Liu and Avner Magen",

year = "2005",

doi = "10.1137/S009753970444572X",

language = "English (US)",

volume = "35",

pages = "627--646",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Sublinear geometric algorithms

AU - Chazelle, Bernard

AU - Liu, Ding

AU - Magen, Avner

PY - 2005

Y1 - 2005

N2 - We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.

AB - We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.

KW - Approximate shortest paths

KW - Polyhedral intersection

KW - Sublinear algorithms

UR - http://www.scopus.com/inward/record.url?scp=33745451951&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33745451951&partnerID=8YFLogxK

U2 - 10.1137/S009753970444572X

DO - 10.1137/S009753970444572X

M3 - Article

AN - SCOPUS:33745451951

SN - 0097-5397

VL - 35

SP - 627

EP - 646

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

Sublinear geometric algorithms

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this