No label defined (Q4728245)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4003525
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4003525 |
Statements
1986
0 references
computational geometry
0 references
geometric location problems in the plane
0 references
time complexity
0 references
optimization problems
0 references
minimum enclosing circle
0 references
largest empty circle
0 references
fixed circle placement
0 references
algorithms
0 references
algebraic computation tree model
0 references
0.8474964499473572
0 references
0.7983908653259277
0 references
0.7871778011322021
0 references
0.7871778011322021
0 references
[For the entire collection see Zbl 0596.00021.] In this paper we discuss a collection of geometric location problems in the plane and their associated time complexity. These problems can be formulated as optimization problems. However, geometric properties are exploited to obtain efficient solutions. Among the problems considered are minimum enclosing circle, largest empty circle, fixed circle placement, and their variations. Most of the algorithms mentioned are asymptotically optimal to within a constant factor under the algebraic computation tree model. Finally, a geometric competitive location problem is discussed and some open problems suggested.
0 references