SFSándor P. Fekete

Sándor P. Fekete

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Sándor P. Fekete has a total of 15 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Online Circle Packing

    by Sándor P. Fekete, Sven von Höveling, Christian Scheffer

    We consider the online problem of packing circles into a square container. A sequence of circles has to be packed one at a time, without knowledge of the following incoming circles and without moving previously packed circles. We present an algorithm that packs any online sequence of circles with a combined area not larger than 0.350389 0.350389 of the square's area, improving the previous best value of {\pi}/10 \approx 0.31416; even in an offline setting, there is an upper bound of {\pi}/(3 + 2 \sqrt{2}) \approx 0.5390. If only circles with radii of at least 0.026622 are considered, our algorithm achieves the higher value 0.375898. As a byproduct, we give an online algorithm for packing circles into a 1\times b rectangle with b \geq 1. This algorithm is worst case-optimal for b \geq 2.36.

  • Open Access

    Connectivity graphs of uncertainty regions

    by Erin Chambers, Alejandro Erickson, Sándor Fekete, Jonathan Lenchner, Jeff Sember, Venkatesh Srinivasan, Ulrike Stege, Svetlana Stolpner, Christophe Weibel, Sue Whitesides

    We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty (BU), each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty (WU), the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty (BCU) problem: Given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are n+k regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty (WCU) problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r.

  • Connectivity Graphs of Uncertainty Regions

    by Erin Chambers, Alejandro Erickson, Sándor P. Fekete, Jonathan Lenchner, Jeff Sember, Venkatesh Srinivasan, Ulrike Stege, Svetlana Stolpner, Christophe Weibel, Sue Whitesides